单调栈的简单应用

青旅半醒 2022-09-12 08:57 313阅读 0赞

栈是一种先进后出的数据结构，只能在栈顶进行元素的入栈和出栈，栈可以使用数组或者是链表进行实现，栈只提供几个受限的操作。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_13_color_FFFFFF_t_70_g_se_x_16][]

单调栈

总的来说分为两种：
    （1）单调递增的栈：就是从栈底到栈顶数据是从大到小
    （2）单调递减的栈：就是从栈底到栈顶数据是从小到大

其实单调栈比较好理解，下面可以结合一些运用场景来进行说明。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_11_color_FFFFFF_t_70_g_se_x_16][]

1、给定一个数组，返回一个等长的数组，对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。如下数组

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

返回的结果如下

int[] result = [4,2,4,-1,-1]

其实很好理解，第一个元素 nums\[0\] 的右边比2大的第一个元素是4，所以 result\[0\] = 4。其他的也是类似的。

最简单的办法就是使用一个双层循环，对于数组中的每一个元素，依次往后查找，如果找到第一个比自己大的，则不继续查找

private int[] solution(int[] nums) {
            int[] result = new int[nums.length];
            //初始化为-1
            Arrays.fill(result, -1);
            //对于每一个元素，依次往后进行查找
            for (int i = 0; i < nums.length - 1; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[j] > nums[i]) {
                        result[i] = nums[j];
                        break;
                    }
                }
            }
            return result;
        }

其实这个问题可以使用单调栈来进行处理。我们可以维护一个单调递增（从栈底到栈顶元素从大到小）的栈。通过下面一个图可以进行解释。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16][]

看上图，当我们查找第一个的右侧比自身大的元素时，后面两个比自身大的是没有意义的，因为会全部被遮住。所以我们只需要保留比当前大的就可以。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_17_color_FFFFFF_t_70_g_se_x_16][]

但是像上面这种，就不可以去掉。

下面我们以如下例子进行说明

int[] nums = {2,1,2,4,3}

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_15_color_FFFFFF_t_70_g_se_x_16][]

（1）处理最后 一 个元素 **3** ，因为栈里面没有值，表示没有比3大的，所以3入栈，同时设置结果数组为-1。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16][]

（2）处理倒数第 二 个元素 **4**，因为要保持栈的单调递增（底到顶大到小），所以元素 3 出栈。3出栈后，栈为空，没有比4大的，设置返回结果数组为-1，同时4入栈。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

（3）处理倒数第 三 个元素 **2，**此时栈不为空，并且栈顶元素 4 比当前处理的元素 2 大，所以我们可以得知，2右边的比 2 大的第一个元素就是4，因为 2 同时比4小，2入栈，也不会破坏栈的单调递增的特性，所以2也得入栈。操作后状态如下图。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

（4）处理倒数第 四 个元素 1 时，因为栈不为空，并且栈顶元素 2 大于操作元素 1，所以元素入栈，同时更新操作结果。如下所示

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

（5）处理第 一 个元素 2，因为栈顶的 2 个元素 1 和 2 都不大于 操作元素 2 ，所以两个元素都要出栈，直到栈顶元素变为4时，表示栈顶元素 4 是 第一个元素 2 右边的第一个大于2的元素。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 4][]

所以最终得到的结果就是

int[] result = {4,2,4,-1,-1}

其实问题的核心就是单调栈的维护，有部分场景下 单调栈 中可能需要存储索引。

private int[] solution(int[] nums) {
            int[] result = new int[nums.length];
    
            //定义单调栈
            Stack<Integer> stack = new Stack<Integer>();
    
            //从后往前进行处理
            for (int i = nums.length - 1; i >= 0; i--) {
    
                //维护单调栈 ：直到变为空栈或者是已经变为了单调栈
                while (!stack.empty() && stack.peek() <= nums[i]) { // 判定个子高矮
                    stack.pop(); // 矮个起开，反正也被挡着了。。。
                }
    
                //如果栈为空，则表示右边不存在比当前操作元素大的值，如果不为空，则栈顶元素就是需要的结果
                result[i] = stack.empty() ? -1 : stack.peek();
    
                //也需要进队，可能会充当左侧元素的第一个比自身大的值
                stack.push(nums[i]);
            }
            return result;
        }

结合代码注释和操作步骤就比较清楚了。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_13_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/159d92699f5e4a0bb8f40bf38faa40e7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_11_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/3d9ef2bbdd854ab89f1481eb6e8fabde.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/75095ac84af8461aa5e371c872cee544.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/de9498b47663451db279178df95d402a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/16cbdbcbcebe499fa029ae3e3a7fd5a8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/908d8a4636144caa88e45ff26cd855ce.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/b003f6d038be4942905b266b51f490f2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/3fdd03dd6a9d4db68f4aad80386918bb.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/63a4ff7efbd64215a591657715d4600c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/b1ae9e30f3184bba9cc5616d98fb22e4.png