Data structure - Stack 小结及leetcode相关题目-526互联

Linear data structure

- Stack

O(1) for push
O(1) for pop
O(1) for top

- Basic skills

先进后出

得到 [0, i] 目前为止subarray nums[:i + 1]的最小值/代表物(TreeNode)，每次将num[i] 和目前的最小值组成tuple放到stack里面

[LeetCode] 155. Min Stack_Easy tag: stack. - 最小值/代表物(TreeNode)，每次将num[i] 和目前的最小值组成tuple放到stack里面
[LeetCode] 654. Maximum Binary Tree_Medium tag: stack - TreeNode，每次将num[i] 组成TreeNode放到stack里面
[LeetCode] 150. Evaluate Reverse Polish Notation_Medium tag: Stack - res，每次将当前的res放到stack里面
[LeetCode] 224. Basic Calculator_Hard tag: stack - res, 每次将当前的res和sign都放进stack里面
[LeetCode] 895. Maximum Frequency Stack_Hard tag: stack - 利用defaultdict（list）, 将每个frequancy的都作为一个stack

- 得到nearest 第一个左边比nums[i]小的，nearest第一个右边比该点小的 => strict increasing stack

考虑以下模板，因为是increase，如果需要强行将所有的num pop，需要将0 或者最小值放进nums

length, 如果不考虑exclusive 比nums[i]小的index，length = right_index - stack[-1] - 1 if stack else right_index

        heights.append(0)
        stack = [] # strict increase stack
        ans = 0
        for index, num in enumerate(heights):
            while stack and heights[stack[-1]] >= num:
                pop_index = stack.pop()
                length = index - stack[-1] - 1 if stack else index
                ans = max(ans, heights[pop_index] * length)
            stack.append(index)
        return ans