栈

栈，是限定仅在表尾进行插入或删除操作的线性表，是一种先进后出，后进先出的数据结构

栈向下生长。即：栈底位于高内存地址，栈顶位于低内存地址

我们知道，函数的调用是通过栈实现的，为啥不用其他数据结构而用栈呢？
原因很简单：在函数的调用过程中，调用者caller和被调用者callee，显然caller比callee存活更久。例如：function A调用B，B调用C，C在返回给B之前，A/B都不能“死”，同样B在返回给A之前，A也不能死。函数调用过程中的函数状态的保存方式与栈的操作机制是完美契合的。这就是使用栈进行函数调用的原因

栈帧

从顶层理解上看，函数调用时，以函数为单位将函数入栈，每个函数都占用栈内存里面一段连续的内存空间，我们把这样的空间块叫做栈帧。也就是说，每个栈帧对应一个函数

每个独立的栈帧一般包括如下3部分:

• 传给这个函数的参数 & 这个函数的返回地址
• 这个函数内部的变量。我们经常说的局部变量存在栈里，其实是存在每一个函数对应的栈帧里，而不是以单个变量为单位进出栈的
• 调用这个函数时的上下文

函数调用的全过程

现在看一下函数调用的过程，不涉及具体的细节，简单的过程逻辑如下：

• 函数入栈: 将函数接收的参数，函数的返回地址，函数体入栈。反正可以理解为就是整个函数部分压入栈，视为一个栈帧，这个栈帧就是这个函数的上下文空间或者说作用域
• 代码跳转: 处理器跳转到被调用函数的入口，执行被调用函数。执行过程中，栈帧内的该函数涉及的变量值会不断被修改
• 函数返回: 被调函数执行完毕后，将返回值返回给调用者，并让程序回到返回地址处继续执行

栈相关问题的核心很简单，就2点——【确定何时入栈 + 确定何时出栈】

例一

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度
例如：
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

这种【最长配对串】的问题，基本上第一思路都是【利用二元栈（我自己定义的，指最多存放两个元素的栈，栈底存放配对串的起始位置的前驱下标，栈顶存放 '('的下标），遇到配对则pop，pop时计算长度】。而有效括号正是非常典型的例题

本题的思路是：
1.遇到'('时发生入栈操作，将其下标入栈；
2.遇到')'则将栈顶元素pop出来，【子串长度 = 当前')'的下标 - pop后栈顶的下标】。根据这个公式，我们需要预先存放一个栈底-1来【标记最初的起始位置的前驱下标】；如"()())"，0入栈，1pop，长度=2=1-(-1)，栈底的作用就是标记有效括号子串的起始位置的前驱
3.遇到')'则将栈顶元素pop出来，pop出来之后，需要栈顶仍有元素（这个元素就是起始位置的前驱）才可根据公式【子串长度 = 当前')'的下标 - pop后栈顶的下标】计算长度，因此pop操作后必须检查stack是否empty，
A.若empty，说明原来的stack中只存在一个元素即起始位置的前驱，而不是'('，如")))()())"就会发生这样的现象，那么前驱被pop了，就需要我们向stack内push一个新的前驱；
B.若非empty，根据公式【子串长度 = 当前')'的下标 - pop后栈顶的下标】计算长度

综上，这个stack最多存放2个元素：[前驱（栈底）, '('（栈顶）]

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = list()
        # 预先放一个栈底-1
        stack.append(-1)
        max_res = 0
        l = len(s)
        for i in range(l):
            # 只有'('，下标入栈
            if s[i] == '(':
                # 下标入栈
                stack.append(i)
            elif s[i] == ')':
                # pop栈顶
                stack.pop(-1)

                # 必须保证栈底前驱的存在
                if not stack:
                    stack.append(i)
                else:
                    max_res = max(max_res, i-stack[-1])
        return max_res

其他做法可见https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode/
这里对其中的双指针算法做出解释：
双指针算法基于这样一个命题——对于一个长度为n的括号字符串，【从左至右扫描时任何时候都有'('计算>=')'计数】 或 【从右至左扫描时任何时候都有')'计算>='('计数】是该括号字符串有效的充分必要条件

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        max_l = 0
        l = len(s)
        # 从左到右，统计'('和')'的个数为left和right，当right>left时，计数归零
        left = right = 0
        for i in range(l):
            if s[i] == '(':
                left += 1
            elif s[i] == ')':
                right += 1
            if right > left:
                left = right = 0
            if left == right:
                max_l = max(max_l, 2*left)
        # 反向，从右到左
        left = right = 0
        for i in range(l-1, -1, -1):
            if s[i] == '(':
                left += 1
            elif s[i] == ')':
                right += 1
            if right < left:
                left = right = 0
            if left == right:
                max_l = max(max_l, 2*left)
        return max_l

例二

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

思路：

• 何时入栈？当【栈为空】时，或者【当前扫描到的柱子高度<=栈顶元素对应的柱子高度】时，不能产生积水，发生一次下标入栈
• 何时出栈？当【当前扫描到的柱子高度>栈顶元素对应的柱子高度】时，即可产生积水，进行如下循环出栈操作：
  • 1.pop当前栈顶元素（容器的底）
  • 2.如果pop后栈为空，当前扫描的柱子下标直接入栈；
    如果pop后栈不为空，取当前扫描柱子的高度和pop后的栈顶元素对应柱子的高度的最小值（也就是取容器长短柱中的短柱），与1中得到的底做差作为容器的可盛水高度，再利用下标求容器长短柱间的距离distance，相乘可得当前扫描柱子与前一可形成容器的柱子间的积水量。计算完毕后继续将当前扫描到的柱子高度与栈顶元素对应的柱子高度做比较来判断是出栈还是入栈

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = list()
        sum_water = 0
        for i in range(len(height)):
            # 每扫描到一个柱子，要么发生【一次入栈】，要么【循环出栈(1到n次)】

            # 未形成积水，一次入栈
            if not stack:
                stack.append(i)
            elif height[i] <= height[stack[-1]]:
                stack.append(i)

            # 形成积水，循环出栈
            elif height[i] > height[stack[-1]]:
                while stack and height[i] > height[stack[-1]]:
                    # 获取底
                    bottom = height[stack.pop(-1)]
                    # 如果栈不为空
                    if stack:
                        # 获取短边长
                        board = min(height[stack[-1]], height[i])
                        # 更新水滴
                        sum_water += (i-stack[-1]-1) * (board - bottom)
                # 当前柱子的下标入栈
                stack.append(i)
        return sum_water

我们发现，无论如何，被扫描到的柱子都是需要入栈的。因此代码可以优化如下：

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = list()
        sum_water = 0
        for i in range(len(height)):

            while stack and height[i] > height[stack[-1]]:
                # 获取底
                bottom = height[stack.pop(-1)]
                # 如果栈不为空
                if stack:
                    # 获取短边长
                    board = min(height[stack[-1]], height[i])
                    # 更新水滴
                    sum_water += (i-stack[-1]-1) * (board - bottom)
            
            # 当前柱子的下标入栈
            stack.append(i)
        return sum_water