Stack: Last in first out Data Structure

發表於 Disqus：
文章字數： 4.8k 所需閱讀時間 ≈ 9 分鐘

本文蒐集

LeetCode 155: Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

Example 1: 

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

  • \(-2^{31}\) <= val <= \(2^{31}\) - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * \(10^4\) calls will be made to push, pop, top, and getMin.

我的解答

class MinStack:

    def __init__(self):
        self.q = []

    def push(self, x):
        curMin = self.getMin()
        if curMin == None or x < curMin:
            curMin = x
        self.q.append((x, curMin));

    def pop(self):
        self.q.pop()


    def top(self):
        if len(self.q) == 0:
            return None
        else:
            return self.q[len(self.q) - 1][0]

    def getMin(self):
        if len(self.q) == 0:
            return None
        else:
            return self.q[len(self.q) - 1][1]

LeetCode 20: Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Example 1: 

Input: s = "()"
Output: true
Example 2: 
Input: s = "()[]{}"
Output: true
Example 3: 
Input: s = "(]"
Output: false
Example 4: 
Input: s = "([)]"
Output: false
Example 5: 
Input: s = "{[]}"
Output: true

Constraints:

  • 1 <= s.length <= \(10^4\)
  • s consists of parentheses only '()[]{}'.

我的解答

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) == 1:
            return False
        
        stack = []
        
        for i in s:
            if i in ('(', '[', '{'):
                stack.append(i)
            else:
                j = None
                if stack:
                    j = stack.pop()
                if i == ')' and j == '(': continue
                elif i == ']' and j == '[': continue
                elif i == '}' and j == '{': continue
                else: break
        
        else:
            if len(stack) == 0:
                return True
        
        return False

LeetCode 739: Daily Temperatures

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

我的解答

class Solution:
    def dailyTemperatures(self, T):
        ans = [0] * len(T)
        stack = []
        for i, t in enumerate(T):
            while stack and T[stack[-1]] < t:
                cur = stack.pop()
                ans[cur] = i - cur
            stack.append(i)

        return ans

LeetCode 150: Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Example 1: 

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2: 
Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3: 
Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Constraints:

  • 1 <= tokens.length <= \(10^4\)
  • tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

我的解答

import math
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        
        for _ in tokens:
            if _ in ("*", "/", "+", "-"):
                x = stack.pop()
                y = stack.pop()
                if _ == '*':
                    stack.append(y * x)
                elif _ == '/':
                    result = y / x
                    if y / x < 0:
                        result = math.ceil(result)
                    else:
                        result = math.floor(result)
                    stack.append(result)
                elif _ == '+':
                    stack.append(y + x)
                else:
                    stack.append(y - x)
            else:
                i = int(_)
                stack.append(i)
        
        return stack[-1]