Posts published in “Stack”

花花酱 LeetCode 150. Evaluate Reverse Polish Notation

By zxi on July 22, 2019

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

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

Note:

Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

Example 1:

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: ["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

Solution: Stack

Use a stack to store the operands, pop two whenever there is an operator, compute the result and push back to the stack.

Time complexity: O(n)
Space complexity: O(n)

C++

class Solution {

public:

int evalRPN(vector<string>& tokens) {

stack<int> s;

for (const string& token : tokens) {

if (isdigit(token.back())) {

s.push(stoi(token));

} else {

int n2 = s.top(); s.pop();

int n1 = s.top(); s.pop();

int n = 0;

switch (token[0]) {

case '+': n = n1 + n2; break;

case '-': n = n1 - n2; break;

case '*': n = n1 * n2; break;

case '/': n = n1 / n2; break;

}

s.push(n);

}

return s.top();

}

};

Python3

# Author: Huahua

class Solution:

def evalRPN(self, tokens: List[str]) -> int:

s = []

for token in tokens:

if token[-1] not in '+-*/':

s.append(int(token))

else:

n2 = s.pop()

n1 = s.pop()

if token == '+': n = n1 + n2

elif token == '-': n = n1 - n2

elif token == '*': n = n1 * n2

elif token == '/': n = int(n1 / n2)

s.append(n)

return s[-1]

Just for fun, f-string with eval

Python3

# Author: Huahua

class Solution:

def evalRPN(self, tokens: List[str]) -> int:

s = []

for token in tokens:

if token[-1] not in '+-*/':

s.append(int(token))

else:

n2 = s.pop()

n1 = s.pop()

s.append(int(eval(f'{n1}{token}{n2}')))

return s[-1]

花花酱 LeetCode 962. Maximum Width Ramp

By zxi on December 25, 2018

Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j]. The width of such a ramp is j - i.

Find the maximum width of a ramp in A. If one doesn’t exist, return 0.

Example 1:

Input: [6,0,8,2,1,5] 
Output: 4 
Explanation:  The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.

Example 2:

Input: [9,8,1,0,1,9,4,0,4,1] 
Output: 7 
Explanation:  The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.

Note:

2 <= A.length <= 50000
0 <= A[i] <= 50000

Solution: Stack

Using a stack to store start candidates’ (decreasing order) index
Scan from right to left, compare the current number with the one on the top of the stack, pop if greater.

e.g.
A = [6,0,8,2,1,5]
stack = [0, 1] => [6, 0]
cur: A[5] = 5, stack.top = A[1] = 0, ramp = 5, stack.pop()
cur: A[4] = 1, stack.top = A[0] = 6
cur: A[3] = 2, stack.top = A[0] = 6
cur: A[2] = 8, stack.top = A[0] = 6, ramp = 2, stack.pop()
stack.isEmpty() => END

C++

// Author: Huahua, running time: 44 ms

class Solution {

public:

int maxWidthRamp(vector<int>& A) {

stack<int> s;

for (int i = 0; i < A.size(); ++i)

if (s.empty() || A[i] < A[s.top()])

s.push(i);

int ans = 0;

for (int i = A.size() - 1; i >= 0; --i)

while (!s.empty() && A[i] >= A[s.top()]) {

ans = max(ans, i - s.top());

s.pop();

}

return ans;

}

};

Python3

# Author: Huahua, running time: 92 ms

class Solution:

def maxWidthRamp(self, A):

s = []

for i in range(len(A)):

if not s or A[i] < A[s[-1]]: s.append(i)

ans = 0

for i in range(len(A) - 1, -1, -1):

while s and A[i] >= A[s[-1]]:

ans = max(ans, i - s.pop())

return ans

花花酱 LeetCode 946. Validate Stack Sequences

By zxi on November 29, 2018

Problem

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Note:

0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed is a permutation of popped.
pushed and popped have distinct values.

Solution: Simulation

Simulate the push/pop operation.

Push element from |pushed sequence| onto stack s one by one and pop when top of the stack s is equal the current element in the |popped sequence|.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 8 ms

class Solution {

public:

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {

stack<int> s;

auto it = begin(popped);

for (int e : pushed) {

s.push(e);

while (!s.empty() && s.top() == *it) {

s.pop();

++it;

}

return it == end(popped);

}

};

Python3

# Author: Huahua, Running time: 40 ms

class Solution:

def validateStackSequences(self, pushed, popped):

s = []

i = 0

for e in pushed:

s.append(e)

while s and s[-1] == popped[i]:

s.pop()

i += 1

return i == len(popped)

花花酱 LeetCode 32. Longest Valid Parentheses

By zxi on October 3, 2018

Problem

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()"

Solution: Stack

Use a stack to track the index of all unmatched open parentheses.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int longestValidParentheses(string s) {

stack<int> q;

int start = 0;

int ans = 0;

for (int i = 0;i < s.length(); i++) {

if(s[i] == '(') {

q.push(i);

} else {

if (q.empty()) {

start = i + 1;

} else {

int index = q.top(); q.pop();

ans = max(ans, q.empty() ? i - start + 1 : i - q.top());

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def longestValidParentheses(self, s):

q = []

start, ans = 0, 0

for i in range(len(s)):

if s[i] == '(':

q.append(i)

continue

if not q:

start = i + 1

else:

q.pop()

ans = max(ans, i - q[-1] if q else i - start + 1)

return ans

Problem

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

An input string is valid if:

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

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Solution: Stack

Using a stack to track the existing open parentheses, if the current one is a close parenthesis but does not match the top of the stack, return false, otherwise pop the stack. Check whether the stack is empty in the end.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 0 ms

class Solution {

public:

bool isValid(string s) {

map<char, char> p{{')', '('}, {']', '['}, {'}', '{'}};

stack<char> st;

for (char c : s) {

if (!p.count(c)) {

st.push(c);

} else {

if (st.empty() || p[c] != st.top()) return false;

st.pop();

}

return st.empty();

}

};

Python3

# Author: Huahua

class Solution:

def isValid(self, s):

p = {')' : '(', ']': '[', '}' : '{'}

stack = []

for c in s:

if c not in p:

stack.append(c)

else:

if not stack or stack[-1] != p[c]: return False

stack.pop()

return not stack

Posts published in “Stack”

花花酱 LeetCode 150. Evaluate Reverse Polish Notation

Solution: Stack

C++

Python3

Python3

花花酱 LeetCode 962. Maximum Width Ramp

Solution: Stack

C++

Python3

花花酱 LeetCode 946. Validate Stack Sequences

Problem

Solution: Simulation

C++

Python3

花花酱 LeetCode 32. Longest Valid Parentheses

Problem

Solution: Stack

C++

Python3

Related Problems

花花酱 LeetCode 20. Valid Parentheses

Problem

Solution: Stack

C++

Python3

Related Problems