Posts published in “Stack”

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:

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

Solution: Stack

1. Using a stack to store start candidates’ (decreasing order) index
2. 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

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:

1. 0 <= pushed.length == popped.length <= 1000
2. 0 <= pushed[i], popped[i] < 1000
3. pushed is a permutation of popped.
4. 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)

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)

Problem

Given a string 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.

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)

Problem

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: [3,1,2,4]
Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.

Note:

1. 1 <= A.length <= 30000
2. 1 <= A[i] <= 30000

Idea

1. order matters, unlike 花花酱 LeetCode 898. Bitwise ORs of Subarrays we can not sort the numbers in this problem.
1. e.g. sumSubarrayMins([3, 1, 2, 4]) !=sumSubarrayMins([1, 2, 3, 4]) since the first one will not have a subarray of [3,4].
2. For A[i], assuming there are L numbers that are greater than A[i] in range A[0] ~ A[i – 1], and there are R numbers that are greater or equal than A[i] in the range of A[i+1] ~ A[n – 1]. Thus A[i] will be the min of (L + 1) * (R + 1) subsequences.
1. e.g. A = [3,1,2,4], A[1] = 1, L = 1, R = 2, there are (1 + 1) * (2 + 1) = 6 subsequences are 1 is the min number. [3,1], [3,1,2], [3,1,2,4], [1], [1,2], [1,2,4]

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

Solution2 : Monotonic Stack

Time complexity: O(n)

Space complexity: O(n)

We can use a monotonic stack to compute left[i] and right[i] similar to 花花酱 LeetCode 901. Online Stock Span

Python3 V2

Mission News Theme by Compete Themes.