单调对列刷题

239. 滑动窗口最大值

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = collections.deque()
        ans = []
        for i in range(len(nums)):
            while queue and nums[queue[-1]] < nums[i]: queue.pop()
            queue.append(i)
            if queue[0] == i - k: queue.popleft()
            if i + 1 < k: continue 
            ans.append(nums[queue[0]])
        return ans
1
2
3
4
5
6
7
8
9
10
11

面试题59 - II. 队列的最大值

class MaxQueue:

    def __init__(self):
        self.queue = collections.deque()
        self.M_queue = collections.deque()

    def max_value(self) -> int:
        return self.M_queue[0] if self.M_queue else -1 


    def push_back(self, value: int) -> None:
        self.queue.append(value)
        while self.M_queue and self.M_queue[-1] < value: self.M_queue.pop()
        self.M_queue.append(value)

    def pop_front(self) -> int:
        if not self.queue:
            return -1
        if self.queue[0] == self.M_queue[0]: self.M_queue.popleft()
        return self.queue.popleft()


# Your MaxQueue object will be instantiated and called as such:
# obj = MaxQueue()
# param_1 = obj.max_value()
# obj.push_back(value)
# param_3 = obj.pop_front()
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

862. 和至少为 K 的最短子数组

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        pre_sum = [0] * (len(nums) + 1)
        for i in range(len(pre_sum) - 1):
            pre_sum[i + 1] = pre_sum[i] + nums[i]
        queue = []
        pos = -1
        ans = 50001
        for i in range(len(pre_sum)):
            while queue and pre_sum[i] - pre_sum[queue[0]] >= k:
                pos = queue[0]
                queue.pop(0)
            if pos != -1:
                ans = min(ans, i - pos)
            while queue and pre_sum[i] < pre_sum[queue[-1]]:
                queue.pop()
            queue.append(i)
        return ans if ans < 50001 else -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1438. 绝对差不超过限制的最长连续子数组

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        q_max = collections.deque()
        q_min = collections.deque()
        i, j = 0, 0
        ans = 0
        for num in nums:
            while q_max and q_max[-1] < num: q_max.pop()
            while q_min and q_min[-1] > num: q_min.pop()
            q_max.append(num)
            q_min.append(num)
            j += 1
            while q_max[0] - q_min[0] > limit:
                if q_max[0] == nums[i]: q_max.popleft()
                if q_min[0] == nums[i]: q_min.popleft()
                i += 1
            ans = max(ans, j - i)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

513. 找树左下⻆的值

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        queue = collections.deque()
        queue.append(root)
        ans = 0
        while queue:
           ans = queue[0].val
           for i in range(len(queue)):
               node = queue.popleft()
               if node.left: queue.append(node.left)
               if node.right: queue.append(node.right)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

135. 分发糖果

class Solution:
    def candy(self, ratings: List[int]) -> int:
        nums = [0] * len(ratings)
        cd = 0
        for i in range(len(ratings)):
            if i and ratings[i] > ratings[i - 1]: cd += 1
            else: cd = 1
            nums[i] = cd
        
        for i in range(len(ratings) - 1, -1, -1):
            if i < len(ratings) - 1 and ratings[i] > ratings[i + 1]: cd += 1
            else: cd = 1
            nums[i] = max(cd, nums[i])
        
        return sum(nums)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

365. 水壶问题

class Solution:
    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:
        def next_state(k, x, y, X, Y): # x 和 y 表示当前状态的容量，X 和Y 表示 x 和 y 杯 的总容量
            if k == 0: return (0, y)
            elif k == 1: return(x, 0)
            elif k == 2: return(X, y)
            elif k == 3: return(x, Y)
            elif k == 4: return(0, y + x) if x + y < Y else (x - (Y - y), Y)
            elif k == 5: return(x + y, 0) if x + y < X else (X, y - (X - x))
            return (-1, -1)
        queue = collections.deque()
        vis = set()
        queue.append((0, 0))
        vis.add((0, 0))
        while queue:
            cur = queue.popleft()
            if cur[0] + cur[1] == targetCapacity or cur[0] == targetCapacity or cur[1] == targetCapacity:
                return True
            
            for i in range(6):
                tmp = next_state(i, cur[0], cur[1], jug1Capacity, jug2Capacity)
                if tmp in vis: continue
                vis.add(tmp)
                queue.append(tmp)
        return False


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

1760. 袋子里最少数目的球

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        def f(nums, k):
            count  = 0
            for i in range(len(nums)):
                count += nums[i] // k
                if nums[i] % k: continue
                count -= 1
            return count
        
        def binary_search(nums, l, r, maxOperations):
            if l == r: return l
            mid = (l + r) // 2
            if f(nums, mid) <= maxOperations: r = mid
            else: l = mid + 1
            return binary_search(nums, l, r, maxOperations)
        return binary_search(nums, max(1, sum(nums) // (len(nums) + maxOperations)), sum(nums) // maxOperations, maxOperations)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

45. 跳跃游戏 II

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) < 2: return 0
        pos = nums[0]
        pre = 1
        count = 1
        while pos + 1 < len(nums):
            max_idx = pre
            for i in range(pre, pos + 1):
                if i + nums[i] > max_idx + nums[max_idx]:
                    max_idx = i
            pre = pos + 1
            pos = max_idx + nums[max_idx]
            count += 1
        return count 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

93. 复原 IP 地址

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def dfs(s, k, ind, ret): # k 表示处理第几段（一共四段）
            if k == 4:
                ## 处理最后一段 
                ## 添加到我们的答案集合
                if len(s) <= ind: return 
                if len(s) - ind > 1 and s[ind] == '0': return 
                num = 0
                for i in range(ind, len(s)):
                    num = num * 10 + ord(s[i]) - ord('0')
                    if num > 255: return 
                ret.append(''.join(s))
                return 

            num = 0
            for i in range(ind, len(s)):
                num = num * 10 + ord(s[i]) - ord('0')
                if num > 255: return 
                if i >= ind + 1 and s[ind] == '0': return 
                tmp = s.copy()
                tmp.insert(i + 1, '.')
                dfs(tmp, k + 1, i + 2, ret)
        s = list(s)
        ret = []
        dfs(s, 1, 0,  ret)
        return ret
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

46. 全排列

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(nums, idx, buff, ans):
            buff.append(nums[idx])
            if len(buff) == len(nums):
                ans.append(buff)
                return 
            for i in range(len(nums)):
                if nums[i] in buff: continue
                tmp = buff.copy()
                dfs(nums, i, tmp, ans)
        ans = []
        for i in range(len(nums)):
            dfs(nums, i, [], ans)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

43. 字符串相乘

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        a = list(map(int, num1[::-1]))
        b = list(map(int, num2[::-1]))
        c = [0] * (len(a) + len(b))
        for i in range(len(a)):
            for j in range(len(b)):
                c[i + j] += a[i] * b[j]
        
        for i in range(len(c)):
            if c[i] < 10: continue 
            if i + 1 == len(c): c.append(0)
            c[i + 1] += c[i] // 10
            c[i] %= 10
        
        while len(c) > 1 and c[-1] == 0:
            c.pop()
        return ''.join(list(map(str, c))[::-1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18