WangBa's Blog

Stack--Monotonic Stack

重学算法系列

发布于：2020年11月23日
次浏览

一、OverView

在前面已经提及过 栈 这个数据结构，在 LeetCode 中有考察过这样一种栈操作：单调栈。

顾名思义，这是在栈的基础上达到单调递增或单调递减的效果。

大概的过程如下：

  • 如果想达到递增的效果：

    • 进栈：首先要比较与栈顶的大小，如果比栈顶元素大，那么直接放在栈顶即可；否则要将栈顶元素出栈，然后将这个元素与栈顶元素进行比较
    • 出栈：直接出栈即可

  • 如果想达到递减的效果：

    • 进栈：首先要比较与栈顶的大小，如果比栈顶元素小，那么直接放在栈顶即可；否则要将栈顶元素出栈，然后将这个元素与栈顶元素进行比较
    • 出栈：直接出栈即可

二、Example

假如有下面的例子：

有一组数为：

1，4，2，5，7，6，8

现在要得到一个单调递增栈，过程如下：

Step Op Stack
1 1 push 1
2 4 push 1 4
3 4 pop | 2 push 1 2
4 5 push 1 2 5
5 7 push 1 2 5 7
6 7 pop | 6 push 1 2 5 6
7 8 push 1 2 5 6 8

三、LeetCode 496

看一个典型例子 LeetCode 0496 :

题意：给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

1
2
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]

分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] nextGreaterElement(int[] nums1, int[] nums2) {

    int[] res = new int[nums1.length];
    Map<Integer, Integer> map = new HashMap<>();
    Stack<Integer> stack = new Stack<>();

    for (int i : nums2) {
        while (!stack.isEmpty() && stack.peek() < i) {
            map.put(stack.peek(), i);
            stack.pop();
        }
        stack.push(i);
    }

    for (int i = 0; i < nums1.length; i++) {
        res[i] = map.get(nums1[i]) != null ? map.get(nums1[i]) : -1;
    }

    return res;

}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://wangba.me/2020/11/23/Stack-Monotonic-Stack/

更新于：2020年11月23日

Leetcode

Algorithm

Stack

评论