Leetcode——单调栈的认识及运用(下一个更大元素 II等)

比眉伴天荒 2022-11-05 11:48 36阅读 0赞

对于栈的认识一开始我只停留在**先进先出**，对于它的运用我并没有过多的思考，知道这两天的刷到才知道我也知道一个概念，那么这个先进先出有什么可以运用，现在的理解是单调递增或者单调递减，可以与栈顶元素比较，比如是单调递增的栈，如果当前元素比栈顶元素小，也就是说是整个栈元素的最小值，就会将栈顶元素弹出，当前元素为栈顶元素，以此类推。对于[这道题，][Link 1]首先要思考我们为什么要用单调栈，是用单调递增还是递减，题目是求的是循环数组的**第一个**比它大的值，也就是说当前元素比栈顶元素大就行，

### 为什么要用单调栈呢？ ###

考虑比较次数，比如对于数组【5，4，3，9】那么也就是说【5，4，3】的第一个比它的元素肯定是9，那么我们还要迭代计算，确实时间复杂度高，那么如果我把【5,4,3】这样存起来那么只要遇到比元素3大，进行栈运算，**比较栈顶元素更换栈顶元素**

### 是递增还是递减？ ###

那么必不可能是递增，如果栈是5，6，7，8这时候出现9，结果就会是\[9,9,9,9\]，可是答案是\[6,7,8,9\],所以肯定是单调递减栈.可以通过举例子去判定用递增还是递减

### 怎么实现循环数组？ ###

这道题一般循环两次就可以了，也就是遍历数组长度的2呗，再通过使用\*\*取模运算 %\*\*可以把下标 ii映射到数组 长度的 0 - N 内。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70]  
采用while一直向下比较，直到遇到比当前元素大的元素

### 单调栈遇到比当前元素大的两种情况 ###

#### 第一种 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 1]

#### 第二种 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 2]

### 代码思想 ###

建立「单调递减栈」，并对原数组遍历一次：

*  如果栈为空，则把当前元素放入栈内；
 *  如果栈不为空，则需要判断当前元素和栈顶元素的大小：
    
     *  如果当前元素比栈顶元素大：说明当前元素是前面一些元素的「下一个更大元素」，则逐个弹出栈顶元素，直到当前元素比栈顶元素小为止。
     *  如果当前元素比栈顶元素小：说明当前元素的「下一个更大元素」与栈顶元素相同，则把当前元素入栈。

class Solution(object):
        def nextGreaterElements(self, nums):
            """ :type nums: List[int] :rtype: List[int] """
            N = len(nums)
            res = [-1] * N
            stack = []
            for i in range(N * 2):
                while stack and nums[stack[-1]] < nums[i % N]:
                    res[stack.pop()] = nums[i % N]
                stack.append(i % N)
            return res

例题  
[1673. 找出最具竞争力的子序列][1673.]  
[739. 每日温度][739.]  
[84. 柱状图中最大的矩形][84.]

--------------------

[1047删除字符中的所有相邻重复项][1047]  
这道题太给力了完全利用栈的优势  
[参考动图便于理解][Link 2]

class Solution:
        def removeDuplicates(self, S: str) -> str:
            stack = []
            for i in S:
                if stack and stack[-1]== i:
                    stack.pop(-1)
                else:
                    stack.append(i)
            return "".join(stack)

--------------------

# 用栈实现递归 #

[224,j基本计算机][224_j]  
[参考大佬][Link 3]  
一个表达式分为三部分：左边表达式①，运算符③， 右边表达式②  
当我们在计算一个表达式的时候，需要先计算左边表达式①，然后需要把①的结果和运算符③保存起来，再需要计算右边表达式②，最后计算①和②的运算。**这个操作就是递归！！**

递归的程序可以用「栈」来模拟：栈为了保存左边表达式①的计算结果和运算符③，在计算右边表达式③的结果之后，从栈中取出运算符③和①的结果，再进行计算整个表达式的结果。

## 代码思想 ##

操作的步骤是：

*  如果当前是数字，那么更新计算当前数字；
 *  如果当前是操作符+或者-，那么需要更新计算当前计算的结果 res，并把当前数字 num 设为0，sign 设为正负，重新开始；
 *  如果当前是 ( ，那么说明遇到了右边的表达式，而后面的小括号里的内容需要优先计算，所以要把res，sign 进栈，更新 res 和 sign 为新的开始；
 *  如果当前是 )，那么说明右边的表达式结束，即当前括号里的内容已经计算完毕，所以要把之前的结果出栈，然后计算整个式子的结果；
 *  最后，当所有数字结束的时候，需要把最后的一个 num 也更新到 res 中。

class Solution(object):
        def calculate(self, s):
            stack = []
            #结果
            res = 0
            #记录正负，1为正，-1为负
            sign = 1
            #记录当前数字
            num = 0
            for i in s:
                # 先判断是否为数字
                if i.isdigit():
                    #如果数字是一位数以上，比如100，得读三次
                    num = num *10 + int(i)
                elif i== '+' or i == '-':
                    #改变res结果
                    res += sign*num
                    #清空读取数据的num，便于下一次读取
                    num = 0
                    #重新更正符号状态
                    sign = 1 if i == '+' else  -1
                elif i == '(':
                    #记录括号前的符号，决定这个括号结果的正负，-(5+4)或者+(5+4),先记录之前的结果再记录符号
                    stack.append(res)
                    stack.append(sign)
                    res = 0
                    #必须重新修改符号状态，如果括号前面之前是负的，不修改会影响后面的计算
                    sign = 1
                elif i == ')':
                    res += sign*num
                    num = 0
                    res *= stack.pop()
                    res += stack.pop()
            #如果题目没有括号，’1+1‘,那么只能通过这一步进行相加减
            res += sign *num
            return res

[Link 1]: https://leetcode-cn.com/problems/next-greater-element-ii/solution/dong-hua-jiang-jie-dan-diao-zhan-by-fuxu-4z2g/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70]: /images/20221023/b76b1a5e8fc74f7496e1155f5e0da279.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 1]: /images/20221023/cd5d974e2cf24ccb8eeb0b26c4961d8c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 2]: /images/20221023/dd0ad65f66824f3d93ee2d0593a8c105.png
[1673.]: https://leetcode-cn.com/problems/find-the-most-competitive-subsequence/
[739.]: https://leetcode-cn.com/problems/daily-temperatures/
[84.]: https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
[1047]: https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/submissions/
[Link 2]: https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/xiang-tong-de-si-lu-cong-zui-chang-di-ze-9kfm/
[224_j]: https://leetcode-cn.com/problems/basic-calculator/submissions/
[Link 3]: https://leetcode-cn.com/problems/basic-calculator/solution/ru-he-xiang-dao-yong-zhan-si-lu-lai-zi-y-gpca/