Algorithm About Stack

Posted on:March 12, 2023 at 01:40 AM
Share on

It’s about the data struct of linear — stack and the Algorithm on it.

Table of contents

Open Table of contents

栈(stack)

栈的关键点

Last in - First out

主要操作复杂度

Java JDK

Stack

实战

  1. 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.
  3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Constraints:

解题思路：

最近相关性，用栈。

class Solution {
    private Stack<Character> a = new Stack();

    public boolean isValid(String s) {
        for(int i=0;i<s.length();i++){
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{'){
                a.push(ch);
            }else {
                if (a.isEmpty()) return false;
                if (ch == ')' && a.pop() != '(') return false;
                if (ch == ']' && a.pop() != '[') return false;
                if (ch == '}' && a.pop() != '{') return false;
            }
        }
        return a.isEmpty();
    }
}
  1. Valid Parenthesis String

Given a string s containing only three types of characters: ’(’, ’)’ and ’*’, return true if s is valid.

The following rules define a valid string:

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "(*)"
Output: true

Example 3:

Input: s = "(*))"
Output: true

Constraints:

class Solution {
    public boolean checkValidString(String s) {
        Stack<Integer> leftStack = new Stack();
        Stack<Integer> starStack = new Stack();
        int n = s.length();
        for(int i=0; i< n;i++){
            char ch = s.charAt(i);
            if (Character.isSpaceChar(ch)) continue;
            if(ch=='('){
                // push i not the char
                leftStack.push(i);
            }else if(ch=='*'){
                starStack.push(i);
            }else {
                if(!leftStack.isEmpty()){
                    leftStack.pop();
                }else if(!starStack.isEmpty()){
                    starStack.pop();
                }else {
                    return false;
                }
            }
        }
        while(!leftStack.isEmpty() && !starStack.isEmpty()){
            int leftIndex = leftStack.pop();
            int starIndex = starStack.pop();
            // If the '(' come after the '*', such as '*(' is not valid
            if(leftIndex>starIndex){
                return false;
            }
        }
        return leftStack.isEmpty();
    }
}
  1. Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

Notes:

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Constraints:

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

class MyQueue {

    Stack<Integer> inStack;
    Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack();
        outStack = new Stack();
    }

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        if(outStack.isEmpty()){
            while(!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
       return outStack.pop();
    }

    public int peek() {
        if(outStack.isEmpty()){
            while(!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
       return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty()&&outStack.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

思路

  1. 定义入栈和出栈
  2. 每次 push 都从入栈 push
  3. 每次出栈的时候，先检查入栈是否是空的，如果不空，将入栈里面的元素先 pop 出去，压入出栈，再冲出栈进行 pop

lc155. Min Stack

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

Implement the MinStack class:

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:

class MinStack {
    private Stack<Integer> values;
    private Stack<Integer> mins;

    public MinStack() {
        values = new Stack();
        mins = new Stack();
    }

    public void push(int val) {
        values.push(val);
        if(mins.isEmpty()) mins.push(val);
        else mins.push(Math.min(val,mins.peek()));
    }

    public void pop() {
        mins.pop();
        values.pop();
    }

    public int top() {
        return values.peek();
    }

    public int getMin() {
        return mins.peek();
    }
}
Share on