本文主要是介绍算法学习 （门徒计划）4-2 单调栈（Monotone-Stack）及经典问题 学习笔记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

算法学习 （门徒计划）4-2 单调栈（Monotone-Stack）及经典问题 学习笔记

• 前言
• 单调栈
• • 基础
  • 性质
  • 代码实现
  • 总结
• 经典例题
• • LeetCode 155. 最小栈 （基础）
  • • 解题思路
  • LeetCode 496. 下一个更大元素 I （单调栈的常见应用1）
  • • 解题思路
    • 示例代码
  • LeetCode 503. 下一个更大元素 II （单调栈的常见应用2）
  • • 解题思路
  • LeetCode 901. 股票价格跨度 （单调栈的常见应用3）
  • • 解题思路
    • 示例代码
  • LeetCode 739. 每日温度
  • • 解题思路
  • LeetCode 84. 柱状图中最大的矩形 （最合适的单调栈例题）
  • • 解题思路
    • 示例代码
  • LeetCode 42. 接雨水
  • • 解题思路
    • 示例代码
  • LeetCode 456. 132 模式
  • • 解题思路
  • LeetCode 907. 子数组的最小值之和 （RMQ与影响力区间）
  • • 解题思路
    • 示例代码
  • LeetCode 1856. 子数组最小乘积的最大值
  • • 解题思路
• 结语

前言

（7.21，百尺竿头）
（本次依旧挑战最短学习时间，3倍耗时，13H以内）
（核心理念是详略得当，把握重点）

本篇为开课吧门徒计划第十一讲4-2 单调栈（Monotone-Stack）及经典问题
（视频是标的第六章第2节： 5-2 单调栈（Monotone-Stack）及经典问题）

本课和上一课同样抽象，先复习一下单调概念，单调表示在该存储结构中，数值以递增或递减的概念排列。上一课是以队列的方式进行排布，而本次则改为用栈。

本课学习的目标是：

• 了解单调栈的性质和应用场景

学习总结（学完后记录）:

• 单调栈是取消了出队功能的单调队列，单调栈不关注区间内最值
• 单调栈是为了关注新元素如何将旧元素序列一分为，关注新值的前一个值或者后一个值
• 单调栈常用于寻找值的区间跨度（某个值之后间隔多少会出现更大或更小的值）
• 单调栈的出元素的方式仅从栈顶出栈
• （额外知识）算法题是为了练习思维模式。

（特殊声明：由于单调栈是单调队列的一种特殊使用，因此有些时候，我依然会习惯的用单调队列来描述问题的解法，但是换成单调栈也是一样的）

单调栈

基础

简要对比单调队列

• 在入队时进行单调性的维护，使得队首元素始终是区间元素的最值
• 维护最大值时应该使用递减队列，最小值时相反

单调队列与栈的联系

• 入队时进行单调性维护都在队尾执行，如果不允许从队首进行出队，那么整体上就是符合单调性的一个栈型结构

单调栈的简单理解

• 单调栈就是不允许从队首出数据的单调队列（栈结构，并且有单调性）
• 由于不需要从队首出元素并且不需要获取队首元素，因此单调栈可以使用栈数据结构。

性质

思考问题：

• 在入栈过程中，什么元素留下，什么元素会被后续元素否决从而剔除

抽象化

假定此时单调性是递增的，那么对于一个震荡序列，从下向上提升一条水平线，当水平线和某一个元素接触时，记录这个元素，并且截除该元素左端的水平线，此时，所有记录的元素将以出现顺序被留下，而所有记录元素之间的元素会被后续元素否决从而被剔除

进一步泛化思维

每一个入栈的元素对于栈（假设是递增）内的元素来说会将元素分为两部分：

• 无法影响的元素（新元素作为这一片元素的最大值，并且符合整体符合单调性）
• 被剔除的元素（新元素作为这一片元素的最小值，并且整体符合单调性）

（整体符合单调性是因为栈内结构本身就符合单调性，因此截取任何一段都是符合单调性的）

可以理解为新元素和其栈内前一个元素相比更大，但是比其剔除的上一个元素小

（等于的情况根据需求讨论）

代码实现

（此处定义等于时，不进行出栈）
（下方的代码可以用上节课单调队列来实现原理，但是为了学习，因此本次用栈来解决）
（下方代码栈内元素为原始元素下标）

        Stack<Integer> stack = new Stack<>();
        for(int i= 0;i<nums.length;i++){
            while(stack.size()>0){
                Integer top = stack.peek();
                if(nums[top]<nums[i]){
                    stack.pop();
                    //todo
                    continue;
                }
                break;
            }
            stack.push(i);
        }

总结

• 单调栈是单调队列的一种特殊运用形式，为了方便理解所以用栈结构进行表示，是一种抽象的概念
• 单调栈更多的是用于关注新元素和旧元素的互动，也就是关注入栈时旧元素如何被新元素一分为二，留下一部分，剔除一部分。
• 单调栈的出元素的方式仅从栈顶出栈（单调队列的队尾）

经典例题

LeetCode 155. 最小栈 （基础）

链接：https://leetcode-cn.com/problems/min-stack

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

解题思路

本题在学过单调队列之后，没有任何难度，上一堂课有一题和这个很像，只是将这个数据结构表示为队列，本题改为栈。

但是存放最值的的目标一直都不用变，因此最值部分依然用单调队列来做，具体操作为：

• 入栈时入栈，同样进行单调队列的入队
• 出栈时出栈，判断队尾元素是否需要出队
• 获取栈顶，从栈顶获取元素
• 获取最值时，从单调队列中获取队首元素

（代码略）

（此处需要明确单调栈的特点就是从栈顶出栈，也就是单调队列的队尾）

LeetCode 496. 下一个更大元素 I （单调栈的常见应用1）

链接：https://leetcode-cn.com/problems/next-greater-element-i

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例 1:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
    对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
    对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
    对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

解题思路

本题的核心在于：请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

（需要注意的是，此处的下一个是指右侧第一个比比较值大的数）

这里就切合了单调栈的思想：单调栈是为了关注新元素如何将旧元素序列一分为，关注新值的前一个值或者后一个值

在本题中nums2将形成旧元素的概念nums1则是新元素，由于nums1来自于nums2，因此由于是期望寻找第一个比期望值大的数字，那么就可以用递减单调队列，当某一个新加入的元素能剔除的元素恰好是num1中的元素时，那么这个新加入的元素就是对应num1元素期望的下一个。

本题用单调栈来描述思路就是：设计一个递减单调栈，但某一个元素入栈时弹出的元素包含num1中的元素时，改元素就是num1中对应元素所求的nums2 中的下一个比其大的值。

（写一遍代码学习一下）

示例代码

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> h = new  HashMap<Integer,Integer> ();

        for(int i = 0;i<nums1.length;i++){
            h.put(nums1[i],-1);
        }

        Stack<Integer> stack = new Stack<>();
        for(int i= 0;i<nums2.length;i++){
            while(stack.size()>0){
                Integer top = stack.peek();
                if(top<nums2[i]){
                    stack.pop();
                    if(h.get(top)!=null){
                        h.put(top,nums2[i]);
                    }
                    continue;
                }
                break;
            }
            stack.push(nums2[i]);
        }

        for(int i = 0;i<nums1.length;i++){
            nums1[i]= h.get(nums1[i]);
        }

        return nums1;
    }
}

LeetCode 503. 下一个更大元素 II （单调栈的常见应用2）

链接：https://leetcode-cn.com/problems/next-greater-element-ii

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

注意: 输入数组的长度不会超过 10000。

解题思路

本题和上一题类似，都是向后寻找下一个能更大的数，因此设计一个递减单调栈，当某一个元素可以出栈时，就输出能使其出栈的元素到结果集中。

因此设计代码为初始化一个结果集合，全部元素为-1，然后用单调栈进行全元素尝试入栈，将所有使得出栈的元素进入结果集合，并且总循环只需要进行两次，如果一个元素已经在结果集中有答案，则不再接受新生成的答案（防止重复遍历的影响）

（代码略）

LeetCode 901. 股票价格跨度 （单调栈的常见应用3）

链接：https://leetcode-cn.com/problems/online-stock-span

编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。

今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。

解题思路

需要明白的概念为，跨度是（从今天开始往回数，包括今天）股票价格小于或等于今天价格的最大连续日数。

因此可以理解为某一个新元素在之前的序列中有几个比起小或者等于的数，这种需求可以使用单调栈来解，并且应该使用单调递减栈，且等于的情况也需要出栈

（本题的设计中，栈内元素应该存储为原始元素的下标，这种方式是一种数据的升维，使得少量的数据空间能表达更多信息量，这是上一节课的额外知识）

（简单做一下本题，再练一下手）

示例代码

(27ms,46.3MB,nice)

class StockSpanner {

    Stack<Integer> stack ;
    ArrayList<Integer> priceList;

    public StockSpanner() {
        stack = new Stack<>();
        priceList = new ArrayList<Integer>();
    }
    
    public int next(int price) {
        priceList.add(price);
        int over = 1;
        Integer top = null;
        while(stack.size()>0){
            top = stack.peek();
            if(priceList.get(top)<=price){
                stack.pop();
                continue;
            }
            break;
        }
        if(stack.size()>0)
            top = stack.peek();
        else
            top = -1;

        over = priceList.size()-top-1;
        stack.push(priceList.size()-1);
        return over;
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

LeetCode 739. 每日温度

链接：https://leetcode-cn.com/problems/daily-temperatures

请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

解题思路

本题可以理解为，对于气温数列，一个新元素入栈时，出栈的元素和其最大跨度为多少（最后一个出栈元素的下标）

由于本题描述为要更高，因此等于的情况不出栈。

（非常简单代码略）

LeetCode 84. 柱状图中最大的矩形 （最合适的单调栈例题）

链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

（需要配图）

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

解题思路

本题和曾经有一题：用木板能框出的最大容量很接近，但是却有一个特殊的限制，矩形面积的高是由最短的矩形决定的。

因此本题可以转换为求任一区间内的最小值，然后再根据区间宽度进行计算，通过枚举找到最大值。
（这是基础解法，必然可行，那么有没有优化一些的思路呢）
（有的，那就是元素对区间的影响力，我称为影响力区间）

因此本题可以转换为求每一个元素能影响的最大区间范围（比如数列中的最小值，其影响的区间就是整个数列），作为这个区间中的最小值。

再进一步转换，可以理解为寻找这个元素左侧第一个比其小的值，和右侧第一个比其小的值，并记录坐标。

而这个找第一个比起小（或者大）的需求，通常用单调栈来实现，因此本题可以设计两个单调递增栈（寻找小值），分别从原始数列的左侧和右侧开始入栈，并记录每一个元素被出栈时，所影响其的元素下标，将其存入某个数组中，最后用这数组中元素的差（首个右侧更小的坐标减去首个左侧更小）就可以计算出每个元素的影响力区间了（ri-li-1），从而可以计算出能生成的矩形面积。

（可能有更多的优化空间，但从学习上，足够了）

（听完课后我意识到，还有进一步的优化空间，那就是计算元素影响区间的方式）
改为：
用一个单调递增栈，当一个元素入栈后，这个元素的前一个元素就是他的区间左侧，当一个元素出栈后，令其出栈的元素就是其区间右侧
（这个方案我没想到是因为对当前课程的知识掌握不彻底，只考虑到单调栈出栈的元素而忘记了栈内元素的关系）

示例代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        int wights []  = new int [heights.length];

        Stack<Integer> stack = new Stack<Integer> ();

        for(int i= 0;i<heights.length;i++){
            while(stack.size()>0){
                Integer top = stack.peek();
                if(heights[top]>heights[i]){
                    wights [top] = i- wights [top]-1;
                    //System.out.println(top+"+"+ wights [top]);
                    stack.pop();
                    continue;
                }
                break;
            }
            if(stack.size()>0)
                wights [i] =stack.peek(); 
            else
                wights [i] = -1;
            stack.push(i);
        }
        while(stack.size()>0){
            Integer top = stack.pop();
            if(stack.size()>0)
                wights [top] = heights.length-stack.peek()-1;
            else
                wights [top] = heights.length;
            //System.out.println(top+"+"+ wights [top]);
        }

        int max = 0;
        for(int i= 0;i<heights.length;i++){
            int s = wights[i]*heights[i];
            if(s>max)
                max = s;
        }

        return max;
    }
}

LeetCode 42. 接雨水

链接：https://leetcode-cn.com/problems/trapping-rain-water

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

解题思路

本题是计算能接多少水，而接的水的区间，由两侧最高的值和中间值占据的空间决定。

并且想象一下，本题会出现两个峰吗？是不会的，因为两个峰就间就可以注满水，因此本题只需要找到数列中的最大值，然后向左和向右寻找最大值并存储，至此生成第一个组结果。

然后再根据第一组结果向内进行注水的判断。

(代码可以优化一下)

本题改为区间两侧出发，向内寻找每一期的最大值，同时进行注水判断，并且记录为左区间注水和右区间注水，并且注水时不进行立即注水，而是尝试性注水，并记录尝试结果，如果在靠拢过程中发现了更大的值则接受尝试结果，如果持续靠拢直到左右尝试区间相遇，那么更矮的区间继续进行尝试，而更高的区间则被放弃。

（这种解法的优势在于只需要常数级别的空间，并且时间效率可能更高）

（如果只是学习，可以只了解方案一，但是想要更高的技术就要跳出掌握的知识框架从现象出发解决问题，此时就不只是学习，而是创新）

（等我完成方案二，大约用了一个小时，值得么？？？）

（那么如果考虑用单调栈怎么做）
方案三：

用单调递减栈，当某元素入栈后，其前一位元素必然比起大，或者没有这个元素，那么其剔除的元素，就是比其小的元素，被剔除的元素就形成了容量。
并且这些容量是一层一层的，每成功计算一次容量，都可以直接存入结果。

（完成了方案三，用时仅半小时，这就是知识的价值，半小时的生命）

示例代码

（方案2）
（1ms，38.1MB）

class Solution {
    public int trap(int[] height) {
        int lp = 0,rp = height.length-1;
        int res = 0,resL = 0,resR = 0;
        int hL =0;
        int hR = 0;
        int prel= lp  ,prer=rp ;
        for(;lp<=rp;lp++,rp--){
            if(height[lp]>=hL){
                res+= resL;
                resL = 0;
                prel = lp;
                hL = height[lp];
 
            }else{
                resL += hL-height[lp];
            }
            if(height[rp]>=hR){
                
                res+= resR;
                resR = 0;
                prer = rp;
                hR = height[rp];

            }else{
                resR += hR-height[rp];
            }
        }
        //System.out.println(lp+"--"+rp+".."+res);
        if(hL>hR){
            for(;rp>prel;rp--){
                if(height[rp]>=hR){
                    res+= resR;
                    resR = 0;
                    hR = height[rp];
                }else{
                    resR += hR-height[rp];
                }
            }
            res+= resR;
        }else{
            for(;lp< prer;lp++){
                //System.out.println(resL);
                if(height[lp]>=hL){
                    res+= resL;
                    resL = 0;
                    hL = height[lp];
                }else{
                    resL += hL-height[lp];
                }
            }
            res+= resL;
        }
        return res;
    }
}

（方案3：单调栈）
（2ms，38.2MB，虽然性能略差，但是代码可读性良好，适合开发时应用）

class Solution {
    public int trap(int[] height) {
        int res = 0;
        Stack<Integer> stack = new Stack<Integer> ();
        int max =0;

        for(int i= 0;i<height.length;i++){
            while(stack.size()>0){
                Integer top = stack.peek();
                if(height[top]<height[i]){
                    stack.pop();
                    if(stack.size()>0){
                        int prei = stack.peek();
                        if( max<height[i])
                            res+= (top - prei)*(max-height[top]);
                        else
                            res+= (top - prei)*(height[i]-height[top]);
                    }
                    continue;
                }
                break;
            }
            if( max<height[i]) max = height[i];

            stack.push(i);
        }
        return res;
    }
}

LeetCode 456. 132 模式

链接：https://leetcode-cn.com/problems/132-pattern

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

示例 3：

输入：nums = [-1,3,2,0]
输出：true
解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。

解题思路

本题需要把握的132模式意思是一个有两个元素的增长序列，此时试图拥有第三元素时发现，新元素需要插入这两个元素之间。

看起来本题可以设计一个递增队列，然后元素入队时，如果能出现新元素使得旧元素出队，并且新元素入队后旧队列内元素至少有两个。

（代码略）

LeetCode 907. 子数组的最小值之和 （RMQ与影响力区间）

链接：https://leetcode-cn.com/problems/sum-of-subarray-minimums

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

示例 1：

输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。

解题思路

本题解起来就是要有一个能力去获取任意区间的最小值，这一题和之前有一题（84. 柱状图中最大的矩形）（刚做的嗷，就在上面）很像，都是要获取任意区间的最小值，本题同理可以用相同的办法去计算所有元素的最大影响区间，在这个区间里，这个元素是最小值。

由此可以获得第一个目标数组，这个数组存储的内容对应原始数组的下标为，对应元素的影响力区间。

并且影响力区间一定是包含关系，因为越小的数字，就可以在更大的范围内作为最小值而存在。

那么本题应该如何根据区间和任意元素的影响力区间表去生成一个快速的由区间到影响力的统计方式呢？

应该根据这个规则，对于任意元素的影响力区间，只要包含了该元素的子区间，则所有子区间的最小值都是该元素。

因此：遍历第一轮获得的影响力区间数组，设计一套计算公式，获得该区间能生成多少种能包含该元素的子集，然后数量乘以元素值，加入最终结果中

其中计算某区间必须包含某元素时最多能生成的子集数的计算方式为：

• 当该元素能从子集合最左移动到最右时，长度就是种类数
• 当该子集合任意移动都能包含该元素时，原始集合长度减去子集合长度就是种类数+1
• 剩余的情况时，该元素和原始集合更近的一边的距离L，就是种类数

换句话说，记录更近的一测距离为a,更远的一侧距离为b：

• 当子集合大小在a，b之间时，此时能生成a种结果
• 当子集合大小小于a时，此时能根据集合大小生成集合大小的结果
• 当子集合大小大于b时，此时原始集合长度减去子集合长度就是种类数+1

（以上是我的解题思路，自认为有些复杂，于是我又有了一个思路，如下：）

本题是一个对任意区间进行求最小值的题目，总体上分为，求最小值和任意区间两个解题切入点，对于区间求最小值其实就是RMQ问题，那么本题就可以转换为依次固定区间末尾，然后在固定后移动区间左侧的RMQ问题（对于RMQ（a，b），当b进行0-len取值时，对a进行0-b的取值遍历）

这种对于RMQ的需求，显然用单调队列来做，因此设计代码如下：
用一个单调递增队列，进行全元素入队。但是每一次入队时后，都从队首全部取出元素进行RMQ（a，b）结果集合的打印，然后再从队首入队，恢复现场，增大b准备下一轮入队。
以上有两种思路：

• 一种使用单调栈，去求所有元素的影响力区间
• 另一种是单调队列，进行RMQ计算获取区间最小值

（但是课上是另一个思路）
继续是理解为RMQ问题，其中每一个入对元素在当前能提供和值，等效于其自身所在范围（bi-1，bi）能计算的和值加上，其之前元素bi能提供的和值。
换句话说回到我提出的第二个思路，当b所在位置固定后，a进行0-b的取值遍历过程中所生成所有区间最小值之和定义为Sbn，由此获得一个数列。这个数列中的元素有个特征，每一个轮次，单调队列的队尾所在的Sbn，等效于，其上一个元素Sbn-1和a从bn-1~bn取值的RMQ（a，b）结果和。
因此，只要每个元素作为结尾的和值Sbn都计算出了，那么当后续新的Sbn想要计算时，只需要其所在单调队列的上一个元素贡献的和值Sbn-1和在范围（bn-1，bn）中进行RMQ求和操作。

（这是利用了单调队列的性质，每个元素在到达队首后，就表示从此时开始到之后的全部范围内，自身都是区间最小值）

（以此为方案3，显然直觉能告诉我，方案3可读性高）

综上：

• 方案1是我提出的元素影响力区间问题，当能获得元素影响力区间后，就可以以某种公式计算出所有子区间的数量，并且以数量进行乘积，最后求和（这个方案需要遍历两轮，并且准备一个数组存入每个元素的影响力区间）
• 方案2是我的提出的RMQ区间问题，性能不佳，课上有在这个模型至上性能更好的方案3（本方案性能不讨论）
• 方案3是课上的思路（有些抽象），需要把握递增序列各个元素的统治力，本质上也是一种区间影响力的计算方式（这个方案需要遍历一轮，并且准备一个数组记录每一个元素作为结尾时能获得的和值）

对比之后我认为课上的方案最佳，我的方案不足
（ε=(´ο｀*)))唉）
（有兴趣的同学可以自行尝试一下其他方案）

示例代码

（方案3）

class Solution {
    private final static Long mod_num = 1000000007L;

    public int sumSubarrayMins(int[] arr) {
        Stack <Integer> stack = new Stack <Integer> ();
        
        Long ans = 0L;
        Long [] sum = new Long [arr.length +1] ;
        sum [0] =0L;
        for(int i=0;i<arr.length;i++){
            while(stack.size()>0&&arr[stack.peek()]>=arr[i]){
                stack.pop();
            }
            int ind = stack.size()>0 ? stack.peek() : -1;
            stack.push(i);
            sum[stack.size()] = (sum[stack.size() - 1] + arr[i] * (i - ind)) % mod_num;
            ans += sum[stack.size()];
            ans %= mod_num;
        }
        return ans.intValue();
    }
}

LeetCode 1856. 子数组最小乘积的最大值

链接：https://leetcode-cn.com/problems/maximum-subarray-min-product

一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。

• 比方说，数组 [3,2,5] （最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。

给你一个正整数数组 nums ，请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大，请你返回答案对 109 + 7 取余 的结果。

请注意，最小乘积的最大值考虑的是取余操作 之前 的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。

子数组 定义为一个数组的 连续 部分。

示例 1：

输入：nums = [1,2,3,2]
输出：14
解释：最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。
2 * (2+3+2) = 2 * 7 = 14 。

解题思路

本题和上一题还是很接近，期望获得一个子数组的最小乘积，和乘积的最大值，一个因数为子数组中的最小值，这个一旦包含了某一个元素就不可变了，另一个饮食是子数组的和，由此本题同样是一个求任意元素的影响力的行为。

通过获取任意元素的影响力区间，又因为所有元素是正数，所以区间范围越大越好，所以可以获取任意元素所在影响力生成的最大乘积值，最终在这个最大乘积值中计算一个最大值即可。

其中为了方便进行区间求和，先需要生成一个求和数列，使得任意区间（a，b）的和等于Sb-Sa。

至此本题所需的两个因数都有办法生成了。

（代码略，核心代码就是生成任意元素的影响力区间的代码，这部分可以从前几题抄）

结语

用时：

• 概念 （课时+笔记整理）
  0.5H+0.5H
• 习题 （课时+思路整理）
  4.75H+0H
• 代码 （有兴趣的题目手写代码）
  4.5H

总计10.25H，近似2倍耗时，进步了

本课学起来非常轻松,我后期跳过了大量的视频内容，这是因为本课的知识是对于上一节课知识运用，由此可以确定，我上一节课学习的很好，这很棒！

但是本课学习也有不足，我又一次发现我的逻辑能力并不足够顺利的将我的思路转换为代码，导致我很可能想到了解题方案，并且也确实能做到，但是实际做到的人力耗时比我想象的高（比如42. 接雨水）。

我的学习方式为，

• 跟着视频学习概念，
• 然后自行先做完全部习题的解题思路，其中不会做的，或者想学习课上解法的，听一下课。（一般来说除非题太简单，我都会听一下课，看看自己的思路是否有优化的空间，如果有我会特别说明）
• 最后补完感兴趣题目的代码

相比起过去的学习方式，我基本省略的内容为：

• 概念部分，自行准备生动形象的举例
• 习题部分，自行解题不会做的题目死磕

从而使得当前我的学习用时能控制在3倍用时以内（10-15H），而不是过去的5倍用时（20-25H），优化学习方式，一直是我在坚持的道路，希望对看到这里的同学有所帮助。

这篇关于算法学习 （门徒计划）4-2 单调栈（Monotone-Stack）及经典问题 学习笔记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！