1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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