算法学习笔记-单调栈

2023-02-27

字数统计: 987字 | 阅读时长≈ 4分

算法学习笔记-单调栈

今天碰到一道题，印象中感觉可以用单调栈做的，但是发现自己一下子想不起来了，所以还是再看看，加深一下印象

单调栈

单调栈可以分为以下两种

单调增栈
单调减栈

单调栈每次操作都保证栈中的值单调递增或递减

单调栈可以解决的问题：

每一个元素左边比该元素大/小且最近的元素以及右边比该元素大/小且最近的元素

例如：

给定一个数组，假设我要找到每个数右边比它小的第一个数

7, 1, 5, 3, 6, 4

则单调栈的过程为：

push 7
1 < 7 故 pop 7 , push 1，得到7右边第一个比它小的值1
5 > 1 故 push 5
3 < 5 故 pop 5, push 3，得到5右边第一个比它小的值3
6 > 3 故 push 6
4 < 6 故 pop 6, push 4，得到6右边第一个比它小的值4

栈内元素从栈顶到栈底分别为： 4 3 1

LeetCode 题

496. 下一个更大元素 I - 力扣（LeetCode）

题目大意：

给定两个数组 nums1,nums2. nums2中的元素包含nums1的元素，但是顺序不同

找出nums2中各元素的右边第一个比它大的值，没有就取-1

按nums1中的顺序返回对应的值

输入：

nums1 = [1, 3, 4] nums2 = [1,3,4,2]

return :

[3, 4, -1]
解释： nums2 中 1 右边第一个比它大的是3,3右边第一个比它大的是4，4之后没有比它大的，所以是-1

代码如下：

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len = nums1.length;
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();
        // 遍历，借助单调栈统计
        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && nums2[i] > stack.peek()) {
                int top = stack.pop();
                map.put(top, nums2[i]);
            }
            map.put(nums2[i], -1); // 暂存 -1 找到后会出栈
            stack.push(nums2[i]);
        }
        int[] res = new int[len];
        int idx = 0;
        for (int num : nums1) {
            res[idx++] = map.get(num);
        }
        return res;
    }
}

官方给出的题解为从后往前遍历，可以省去处理栈的部分，因为栈是先进后出的结构

for (int i = nums2.length - 1; i >= 0; --i) {
    int num = nums2[i];
    while (!stack.isEmpty() && num >= stack.peek()) {
         stack.pop();
    }
    map.put(num, stack.isEmpty() ? -1 : stack.peek());
    stack.push(num);
}

503. 下一个更大元素 II - 力扣（LeetCode）

题目大意：

给定一个环形数组，找出每一个元素后比它大的第一个数

输入：

nums = [1,2,3,4,3]

return:

[2,3,4,-1,4]

因为添加了一个环形条件，就相当于既包括后面，又包括前面

我们可以在处理时将数组复制后添加在原数组后面

具体处理为：取数组长度的两倍，然后索引值取 nums[i % len]，为了方便存储结果，我们在栈中存储索引值

代码如下：

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int len = nums.length;
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            res[i] = -1;
        }
        for (int i = 0; i < 2 * len - 1; i++) {
            while (!stack.isEmpty() && nums[i%len] > nums[stack.peek()]) {
                int idx = stack.pop();
                res[idx] = nums[i%len];
            }
            stack.push(i%len);
        }
        return res;
    }
}

556. 下一个更大元素 III - 力扣（LeetCode）

题目大意：

给定一个正整数 n ，找出：由重新排列 n 中存在的每位数字组成，并且其值大于 n的最小整数。不存在返回 -1 。

并且要求返回的整数是32 位整数，如果答案不是 32 位整数返回 -1

示例：

输入: n = 12
输出: 21


输入: n = 21
输出: -1

解题思路：

给的示例比较简单，我们换一个数字

输入: 12443322
输出: ?

我们先出满足题意的答案，即比该数字大的且最接近他的数字

13222344

本文作者： Naskete
本文链接： https://Naskete.github.io/2023/02/27/algorithm/算法学习笔记-单调栈/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！