71. 简化路径

知识点： 用队列实现栈 Deque, ArrayDeque, pollLast, offer, equals, split, join.

class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<String>();
        for (String p : path.split("/")) {
            if ("..".equals(p)) {
                if (!stack.isEmpty()) stack.pollLast();
            } 
            else if (p.length() > 0 && !".".equals(p)) {
                stack.offerLast(p);
            }
        }
        // StringBuilder ans = new StringBuilder();
        // if (stack.isEmpty()) ans.append('/');
        // else {
        //     while (!stack.isEmpty()) {
        //         ans.append('/');
        //         ans.append(stack.pollFirst());
        //     }
        // }
        // return ans.toString();

        return "/" + String.join("/", stack);
    }
}

239. 滑动窗口最大值

heapq 库中的堆默认是最小堆

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: 
    	## 方法一：优先队列 最大堆
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)
        res = [-q[0][0]]
        for i in range(k, len(nums)):
            heapq.heappush(q, (-nums[i], i))
            while q[0][1] <= i - k: heapq.heappop(q)           
            res.append(-q[0][0])
    
        return res

    	## 方法二：双向队列
        q = collections.deque()
        # for i in range(k):
        #     while q and nums[i] >= nums[q[-1]]:q.pop()
        #     q.append(i)
        for i in range(k - 1, -1, -1):
            if not q or nums[i] > nums[q[-1]]: q.append(i)
        q.reverse() # 对应值单调递减

        res = [nums[q[0]]]
        for i in range(k, len(nums)):
            while q and nums[i] >= nums[q[-1]]: q.pop()
            q.append(i) # 去掉小的后添加 维护对应值单调递减队列
            while q[0] <= i - k: q.popleft() # 移出窗口
            res.append(nums[q[0]])
        
        return res

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

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        res = n + 1
        # acc = [0] + list(accumulate(nums)) 
        acc = [0]
        for x in nums: acc.append(acc[-1] + x)     
        q = collections.deque()
        for i, x in enumerate(acc):
            while q and x <= acc[q[-1]]:
                q.pop()
            while q and x - acc[q[0]] >= k:
                res = min(res, i - q.popleft())
            q.append(i)                
        return res if res <= n else -1

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        int ans = n + 1;
        long[] acc = new long[n + 1];
        Deque<Integer> q = new LinkedList();
        for (int i = 0; i < n; i++) acc[i + 1] = acc[i] + (long) nums[i];
        for (int i = 0; i < acc.length; i++){
            while (!q.isEmpty() && acc[i] <= acc[q.getLast()]) q.removeLast();
            while (!q.isEmpty() && acc[i] >= acc[q.getFirst()] + k) ans = Math.min(ans, i - q.removeFirst());
            q.addLast(i);
        }
        return ans <= n ? ans : -1; 
    }
}

1823. 找出游戏的获胜者

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        q = deque(range(1, n + 1))
        while len(q) > 1:
            for _ in range(k - 1):
                q.append(q.popleft())
            q.popleft()
        return q[0]

class Solution {
    public int findTheWinner(int n, int k) {
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 1; i < n + 1; i++) q.offer(i);
        while (q.size() > 1){
            for (int i = 1; i < k; i++){
                q.offer(q.poll());
            }
            q.poll();
        }
        return q.peek();
    }
}

约瑟夫环

第一轮会删掉第 k 个人，问题就变为对 n - 1 个人进行这个游戏。
假设我们知道 f(n?1, k) 最终剩下的人的编号，由于我们删了第 k 个人，n ? 1 个人的游戏是从原来第 k + 1 个人开始的，原来的编号和新的编号有一个偏差 k。
以坐标从 0 到 n - 1 来看的话（去掉 1 的偏差减少计算量，最终加一次 1 即可）：
f(n, k) = (f(n - 1, k) + k) \ % n
当只剩一个人时，即 f(1, k) = 0
从 f(1, k) 推出 f(2, k) 一直到 f(n, k)即可。

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        ans = 0
        for i in range(2, n + 1):
            ans = (ans + k) % i
        return ans + 1

每次往同一方向，以固定步长 k 进行消数。由于下一次操作的发起点为消除位置的下一个点（即前后两次操作发起点在原序列下标中相差 kk），同时问题规模会从 n 变为 n - 1，因此原问题答案等价于 findTheWinner(n - 1, k) + k。

一些细节，由于编号从 1 开始，在返回答案时我们需要将结果为 0 的值映射回编号 n。

class Solution {
    public int findTheWinner(int n, int k) {
        if (n <= 1) return n;
        int ans = (findTheWinner(n - 1, k) + k) % n;
        return ans == 0 ? n : ans;
    }
}