9. 栈相关

Q20. 有效的括号 EASY

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 示例 1: 输入: “()” 输出: true 示例 2: 输入: “()[]{}” 输出: true 通过次数299,483 | 提交次数717,260

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        d = {')':'(',']':'[','}':'{'}
        for i in s:
            if i in d:
                p = stack.pop() if stack else ' '
                if d[i]!=p:
                    return False
            else:
                stack.append(i)
        return not stack
class Solution:
    def isValid(self, s: str) -> bool:
        while '{}' in s or '()' in s or '[]' in s:
            s = s.replace('{}','')
            s = s.replace('[]','')
            s = s.replace('()','')
        return not s

Q32. 最长有效括号 HARD

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。 示例 1: 输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()” 示例 2: 输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()” 通过次数62,431 | 提交次数203,113

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack,res = [],[0]*len(s)
        for i,v in enumerate(s):
            if v is '(':
                stack.append(i)
            else:
                if stack:
                    res[stack.pop()],res[i] = 1,1
        temp,r = 0,0
        for i in res:
            if i == 1:
                temp+=1
            else:
                r = max(temp,r)
                temp= 0
        return max(temp,r)

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> res(n,0);
        stack<int> stac;
        for (int i=0;i<n;i++)
        {
            if (s[i] == '(')  stac.emplace(i);
            else{
                if (!stac.empty())
                {
                    res[stac.top()] = 1;
                    res[i] = 1;
                    stac.pop();
                }
            }
        }
        int temp=0,tmp=0;
        for(auto& it:res)
        {
            if (it==1) temp+=1;
            else{
                tmp = max(temp,tmp);
                temp = 0;
            }
        }
        return max(temp,tmp);
    }
};

Q155. 最小栈 EASY

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。 示例: 输入： [“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”] [[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2] 解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); —> 返回 -3. minStack.pop(); minStack.top(); —> 返回 0. minStack.getMin(); —> 返回 -2. 通过次数128,483 | 提交次数235,510

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_stack = [math.inf]


    def push(self, x: int) -> None:
        self.stack.append(x)
        self.min_stack.append(min(x,self.min_stack[-1]))


    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()


    def top(self) -> int:
        return self.stack[-1]


    def getMin(self) -> int:
        return self.min_stack[-1]

Q224. 基本计算器 HARD

实现一个基本的计算器来计算一个简单的字符串表达式的值。 字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。 示例 1: 输入: “1 + 1” 输出: 2 示例 2: 输入: “ 2-1 + 2 “ 输出: 3 示例 3: 输入: “(1+(4+5+2)-3)+(6+8)” 输出: 23 说明： 你可以假设所给定的表达式都是有效的。 请不要使用内置的库函数 eval。 通过次数14,846 | 提交次数39,047

class Solution:
    def calculate(self, s: str) -> int:

        def bracket(stack):
            temp = 0
            flag = 1
            while stack:
                a = stack.pop()
                if a != ')':
                    if a == '+':
                        flag = 1
                    elif a == '-':
                        flag = -1
                    else:
                        while stack and stack[-1].isdigit():
                            a += stack.pop()
                        a = int(a)
                        temp +=a*flag
                else:
                    break
            return temp
        s = s.replace(' ','')
        stack = []
        for i in s[::-1]:
            if i == '(':
                stack.append(bracket(stack))
            else:
                stack.append(i)
        return bracket(stack)

Q150. 逆波兰表达式求值 MEDIUM

据 逆波兰表示法，求表达式的值。 有效的运算符包括 +, -, , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 说明： 整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。 示例 1： 输入: [“2”, “1”, “+”, “3”, ““] 输出: 9 解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) 3) = 9 逆波兰表达式： 逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) ( 3 + 4 ) 。 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) ) 。 逆波兰表达式主要有以下两个优点： 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + 也可以依据次序计算出正确结果。 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中 通过次数41,686 | 提交次数82,811

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        f1 = lambda a,b:a+b
        f2 = lambda a,b:a-b
        f3 = lambda a,b:a*b
        f4 = lambda a,b:int(a/b)
        maps = {'+':f1,'-':f2,'*':f3,'/':f4}
        stack = []
        for i in tokens:
            if i in maps:
                a = stack.pop()
                b = stack.pop()
                stack.append(maps[i](b,a))
            else:

                stack.append(int(i))
        return stack[-1]

Q316. 去除重复字母 HARD

Q402. 移掉K位数字 MEDIUM

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。 注意: num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 示例 1 : 输入: num = “1432219”, k = 3 输出: “1219” 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。 示例 2 : 输入: num = “10200”, k = 1 输出: “200” 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。 示例 3 : 输入: num = “10”, k = 2 输出: “0” 解释: 从原数字移除所有的数字，剩余为空就是0。 通过次数18,909 | 提交次数65,000

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        def remove(num):
            for i in range(len(num)-1):
                if num[i] > num[i+1]:
                    return num[:i]+ num[i+1:]
            return num[:-1]

        for i in range(k):
            # print(f'{i}th num={num}')
            if num:
                num = remove(num).lstrip('0')
            if not num:
                return '0'

            '''num = remove(num).lstrip('0') if num else '0'
            if num == '0' or not num:
                return '0' '''

        return num