Stack
232. Implement Queue using Stacks
Implement a first in first out (FIFO) queue using only two stacks.
class MyQueue {
// 初始化入口
private Stack<Integer> inStack = new Stack<>();
// 初始化出口
private Stack<Integer> outStack = new Stack<>();
public MyQueue() {
}
public void push(int x) {
inStack.push(x);
}
public int pop() {
if(empty()) return -1;
if(outStack.isEmpty()) {
// 如果出口没有数据，但是入口有数据
// 需要入口的数据反转到出口，
// 那出口的第一个元素就是相对最先加入的元素，也就是队头
while(!inStack.isEmpty()) outStack.push(inStack.pop());
}
return outStack.pop();
}
public int peek() {
if(empty()) return - 1;
if(outStack.isEmpty()) {
while(!inStack.isEmpty()) outStack.push(inStack.pop());
}
return outStack.peek();
}
public boolean empty() {
// 如果入口和出口都没有元素，那就空了
return inStack.isEmpty() && outStack.isEmpty();
}
}
225. Implement Stack using Queues
Implement a last-in-first-out (LIFO) stack using only two queues
class MyStack {
private Queue<Integer> inQueue = new LinkedList<>();
private int size; // **这里是关键，要记录大小，不然没有size - 1可用
public MyStack() {}
public void push(int x) {
inQueue.offer(x);
size ++;
}
/**
* 如何拿到队列的最后一个元素？
*/
public int pop() {
if(empty()) return -1;
// 新建一个临时队列，保存数据
Queue<Integer> tempQueue = new LinkedList<>();
for(int i = 0; i < size - 1; i++) {
// 将队列弹出size - 1个元素，依次加入临时队列
// 剩下的一个就是最后一个元素，对应栈顶
tempQueue.offer(inQueue.poll());
}
int result = inQueue.poll();
// 这里需要再次将出队的数值从tempQueue中再加回去
inQueue = tempQueue; // 将临时队列重新指向给inQueue
size --; // 记得减少数量
return result;
}
public int top() {
if(empty()) return -1;
int result = pop();
push(result); // 用完记得要加回去
return result;
}
public boolean empty() {
return size == 0;
}
}
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:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
class Solution {
public boolean isValid(String s) {
// 如果长度是奇数，直接不满住
if(s.length() % 2 == 1) return false;
// 新建stack; character而不是charactor!!!
Stack<Character> stack = new Stack<>();
// 转换为字符数组
char[] chars = s.toCharArray();
for(char c : chars) {
// 如果放入的是正括号，直接放入其反括号，便于后续比较
if(c == '(') {
stack.push(')');
continue;
}
if(c == '{') {
stack.push('}');
continue;
}
if(c == '[') {
stack.push(']');
continue;
}
// 如果还有字符，又是反括号，但是栈中已经空了，
// 没有正括号了，说明肯定不合法
if(stack.isEmpty()) return false;
// 弹出栈顶符号如果不匹配，直接返回false
if(stack.pop() != c) return false;
}
// 最终括号肯定都是要匹配消除的，如果栈不为空，说明未完全匹配
return stack.isEmpty();
}
}
921. Minimum Add to Make Parentheses Valid
A parentheses string is valid if and only if:
- It is the empty string,
- It can be written as AB (A concatenated with B), where A and B are valid strings, or
- It can be written as (A), where A is a valid string. You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.
- For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))". Return the minimum number of moves required to make s valid. Example 1: Input: s = "())" Output: 1 Example 2: Input: s = "(((" Output: 3
class Solution {
/**
* 使用栈的解法
*/
public int minAddToMakeValid(String s) {
int len = s.length();
if(len == 0) return 0;
Stack<Character> myStack = new Stack<>();
// 举例：
// ()); 1-> ['(']; 2-> ['(', ')'] => []; 3-> [')']
// "(((" 1-> ['(']; 2-> ['((']; 3-> ['(((']
// 总结：不停往栈中丢，如果左括号和有括号匹配，出栈；否则入栈
for (int i = 0; i < len; i++) {
Character c = s.charAt(i);
if(myStack.isEmpty()) {
myStack.push(c);
continue;
}
if(myStack.peek() == '(' && c == ')') {
myStack.pop();
continue;
}
myStack.push(c);
}
return myStack.size();
}
}
class Solution {
/**
* 这里不需要用到栈，所以更快
*/
public int minAddToMakeValid(String s) {
int leftSize = 0; // 左括号不匹配数量
int rightSize = 0; // 右括号不匹配数量
for(int i = 0; i < s.length(); i ++) {
char c = s.charAt(i);
// 遇到左括号：leftSize + 1
if(c == '(') {
leftSize ++;
continue;
}
// 遇到右括号，右括号去消除左括号的数量
// 这里有个思考的地方，为什么左括号数量大于0，就可以减去左括号的数量，
// 如果上一个字符也是右括号呢？不就不能减了
// 问题是上一个如果是右括号，那上一个括号应该也判断了
// 也就是有没有左括号大于0，但是上一个括号是右括号的情况
// => ((() <= ')'? 不可能，上一个括号会消掉左括号
if(c == ')') {
if(leftSize > 0) leftSize --; // 如果未匹配左括号大于0；消掉
else rightSize ++; // 否则右括号不匹配数量+1
}
}
return leftSize + rightSize; // 左右括号不匹配的数量和
}
}
856. Score of Parentheses
Given a balanced parentheses string s, return the score of the string. The score of a balanced parentheses string is based on the following rule:
- "()" has score 1.
- AB has score A + B, where A and B are balanced parentheses strings.
- (A) has score 2 * A, where A is a balanced parentheses string. Example 1: Input: s = "()" Output: 1 Example 2: Input: s = "(())" Output: 2 Example 3: Input: s = "()()" Output: 2
class Solution {
public int scoreOfParentheses(String s) {
// 核心是计算完后，再把结果丢到栈里
// 共有，3种情况
// () = 1 直接匹配
// (()) = (1) = 2 * 1 嵌套匹配
// ()() = 1 + 1 = 2 非嵌套匹配
if(s.length() == 0) return 0;
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(stack.isEmpty()) {
// 这里用-1代表左括号
// 因为是匹配的括号，所以第一个肯定是(
stack.push(-1);
continue;
}
// 如果还是左括号
if(c == '(') {
stack.push(-1);
continue;
}
// 匹配上：栈顶元素为-1，说明是左括号，和当前右括号匹配
if(stack.peek() == -1 && c == ')') {
stack.pop(); // 将左括号弹出
stack.push(1); // 入栈匹配括号数量：1
continue;
}
// 如果栈顶元素不是-1，说明是上一次的计算结果
if(stack.peek() != -1) {
int num = 0;
// 将计算的数字全部弹出并且相加
while(stack.peek() != -1) {
num += stack.pop();
}
num = num * 2; // 说明是(A+B+..)这种情况
stack.pop(); // 弹出左括号
stack.push(num); // 加入计算好的值
}
}
// 最后弹出所有累加的数字
int result = 0;
while(!stack.isEmpty()) result += stack.pop();
return result;
}
}
227. Basic Calculator II
Given a string s which represents an expression, evaluate this expression and return its value. The integer division should truncate toward zero. You may assume that the given expression is always valid. All intermediate results will be in the range of [-2(31), 2(31) - 1]. Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
- Example 1: Input: s = "3+2*2" Output: 7
- Example 2: Input: s = " 3/2 " Output: 1
- Example 3: Input: s = " 3+5 / 2 " Output: 5
class Solution {
public int calculate(String s) {
int len = s.length();
// 字符串中包含空格，如何过滤掉？
Stack<Integer> stack = new Stack<>();
int num = 0;
char prevOp = '+';
for(int i = 0; i < len; i++) {
char c = s.charAt(i);
// 判断字符是否数字, 因为每次只能取一个字符，
if(Character.isDigit(c)) {
// 如果数字是两位，那就凉了，所以要累加
// 前一个乘以10 + 当前的
// 这里记住，直接减去'0'得到数字
num = num * 10 + (c - '0');
}
// 这里为什么要判断i?
// 因为循环到字符串末尾，已经不可能是字符了
// 此刻就要判断了
// 总之：开始计算的条件是要么遇到运算符，要么到达循环的末尾
if (!Character.isDigit(c) && c != ' ' || i == len - 1) {
switch(prevOp) {
case '+' :
stack.push(num);
break;
case '-' :
stack.push(-num);
break;
case '*' :
stack.push(stack.pop() * num);
break;
case '/' :
stack.push(stack.pop() / num);
break;
}
prevOp = c;
num = 0;
}
}
int result = 0;
while(!stack.isEmpty()) result += stack.pop();
return result;
}
}
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(int 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. You must implement a solution with O(1) time complexity for each function. 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
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
stack.push(x);
if(minStack.isEmpty()) {
minStack.push(x);
return; // 这里忘了return 也是巨坑
}
// 这里有坑，小于等于都要放，
// 如果出栈把最小值出掉，前面还有最小值，那就不对了
if(x <= minStack.peek()) {
minStack.push(x);
}
}
public void pop() {
if(stack.isEmpty()) return;
int val = stack.pop();
// 如果最小栈的栈顶元素等于出栈元素
// 最小栈出栈
if(minStack.peek() == val) minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
if(minStack.isEmpty()) return -1;
return minStack.peek();
}
}
496. Next Greater Element I
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array. You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2. For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1. Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.
- Example 1:
- Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
- Output: [-1,3,-1]
- Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- Example 2:
- Input: nums1 = [2,4], nums2 = [1,2,3,4]
- Output: [3,-1]
- Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.
class Solution {
/**
* 把数组的元素想象成并列站立的人，元素大小想象成人的身高。
* 这些人面对你站成一列，如何求元素「2」的 Next Greater Number呢？
* 很简单，如果能够看到元素「2」，
* 那么他后面可见的第一个人就是「2」的Next Greater Number，
* 因为比「2」小的元素身高不够，都被「2」挡住了，第一个露出来的就是答案。
--------
| -------
--------------------| |
| -------| | |
| | | | |
2 1 2 4 3
4 2 4 -1 -1
*/
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
// 这里为什么要使用map，因为说了nums1是nums2的自己
// 那直接判断nums2里的元素就可以了
Map<Integer, Integer> map = new HashMap<>();
// 由于Vector由于效率问题已经被弃用，
// 因此继承Vector的Stack也存在效率问题，故不推荐使用。
// Stack<Integer> stack = new Stack<>();
Deque<Integer> deque = new ArrayDeque<>();
for(int i = nums2.length - 1; i >= 0; i --) {
int curVal = nums2[i];
// 在当前这个curVal，比他小(矮)的元素全部出队
while(!deque.isEmpty() && curVal > deque.peek()) deque.pop();
// 当前元素，下一个大的元素，要么栈空了是-1
// 要么栈里面还有比他高的，就是下一个比他大的值
map.put(curVal, deque.isEmpty() ? -1 : deque.peek());
// 自己入队
deque.push(curVal);
}
// 因为要返回数组
int[] arr = new int[nums1.length];
for(int i = 0; i < nums1.length; i++) {
arr[i] = map.get(nums1[i]);
}
return arr;
}
}
901. Online Stock Span
Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day. The span of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.
- For example, if the price of the stock in the last four days is [7,2,1,2] and the price of the stock today is 2, then the span of today is 4 because starting from today, the price of the stock was less than or equal 2 for 4 consecutive days.
- Also, if the price of the stock in the last four days is [7,34,1,2] and the price of the stock today is 8, then the span of today is 3 because starting from today, the price of the stock was less than or equal 8 for 3 consecutive days. Implement the StockSpanner class:
- StockSpanner() Initializes the object of the class.
- int next(int price) Returns the span of the stock's price given that today's price is price. Example 1: Input ["StockSpanner", "next", "next", "next", "next", "next", "next", "next"][], [100], [80], [60], [70], [60], [75], [85]] Output [null, 1, 1, 1, 2, 1, 4, 6]
class StockSpanner {
/**
* 这里构建一个对象用来
*/
class Pair {
int price; // 值
int count; // 数量
public Pair(int price, int count) {
this.price = price;
this.count = count;
}
}
// 这里大家都用deque，效率更高
private Deque<Pair> deque;
public StockSpanner() {
deque = new ArrayDeque<>();
}
/**
* 查找比当前小的之前的个数和？
* 维护单调递减栈
* 栈里保存的元素有：当前数量+ 小于等于当前数值的个数和
*/
public int next(int price) {
if(deque.isEmpty()) {
// 全部操作队尾，模拟栈
deque.offerLast(new Pair(price, 1));
return 1;
}
int count = 1; // 自己本身也算一次
// 找出比当前值小的记录，全部出栈
// 核心是：之前有没有比我小的？有的话告诉我你的count是什么？
// 因为后面的元素比较到比自己大的元素就得停止
while(!deque.isEmpty() && deque.peekLast().price <= price) {
// 累加比当前price小的数量
// 全部操作队尾，模拟栈
count += deque.pollLast().count;
}
// 再次放进栈中，供下一次判断使用
deque.offerLast(new Pair(price, count));
return count;
}
}