LeetCode: Monotonic Stack 单调栈

 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
// 定义一个单调栈
Deque<Integer> stack = new LinkedList<>();
// 第一个元素，直接添加
stack.push(0); // 这里存的是数组下标
for (int i = 1; i < nums.length; i++) {
    // 单调递增栈这里就是大于，即 nums[i] > nums[deque.peek()]
    if (nums[i] < nums[stack.peek()]) {
        stack.push(i);
    } else if (nums[i] == nums[stack.peek()]) {
        stack.push(i);
        // 此处除了入栈，在有些场景下，还有可能有其他操作
        // ..............
    } else {
        // 循环比较，直到遇到当前元素小于栈顶的元素情况，跳出循环
        // 单调递增栈，这里是小于，即nums[i] < nums[deque.peek()]
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            //主要逻辑
            // ............
            // ............
            // 弹出栈顶元素
            stack.pop();
        }
        stack.push(i);
    }
}