week report 2024.15
Why grow up? and why they didn't.
Entertainment¶
Nah
Learning¶
Graph with PQ¶
- use pq to calculate least steps
class Solution:
def minimumTime(
self, n: int, edges: List[List[int]], d: List[int]
) -> List[int]:
adj = defaultdict(list)
for u, v, l in edges:
adj[u].append((l, v))
adj[v].append((l, u))
# use sys.maxsize to mark non-reachable
res = [sys.maxsize] * n
# (cost, index)
pq = [(0, 0)]
while pq:
cost, i = heapq.heappop(pq)
if res[i] > cost:
res[i] = cost
# to next index, and check accessibility
for (c, j) in adj[i]:
nc = cost + c
if nc < d[j] and nc < res[j]:
heapq.heappush(pq, (nc, j))
# update non-reachable index
for i in range(n):
if res[i] == sys.maxsize:
res[i] = -1
return res
MonotonicStack¶
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
# (index, height), the start index which could form rectangle with height
stk = []
res = 0
for i, h in enumerate(heights):
# reserve start_index with i
start_index = i
# pop out greater ones from stk
# update maximal area, also the feasible index of current h to previous index
while stk and stk[-1][1] > h:
index, height = stk.pop()
res = max(res, height * (i - index))
start_index = index
stk.append((start_index, h))
# if stack is not empty, the left parts, it's non-decreasing order
# [2,1,5,6,2,3]
# [(4,2), (5,3)]
for i, h in stk:
res = max(res, h * (n - i))
return res
life¶
- leetcode contests are overwhelmingly hard for me
Sharing¶
We tend to measure performance by what happens when things are going well. Yet how people, organizations, companies, leaders, and other things do on their best day isn’t all that instructive. To find the truth, we need to look at what happens on the worst day.
References¶
overall, very useful sharing.