1. 力扣155：最小栈
1.1 题目：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
示例 1:
输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]输出： [null,null,null,null,-3,null,0,-2]解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
提示：
-231 <= val <= 231 - 1pop、top和getMin操作总是在 非空栈 上调用push,pop,top, andgetMin最多被调用3 * 104次
1.2 思路：
可以用优先队列的思想（堆）解决，也可以用单调栈。思路都是让每次找到最小的元素的时间复杂度为O(1)。优先队列每次弹出最小值，单调栈每次也弹出最小值。
1.3 题解1: 单调栈
java">class MinStack {Deque<Integer> stack1;Deque<Integer> stack2;public MinStack() {stack1 = new LinkedList<>();// stack2是单调栈stack2 = new LinkedList<>();}public void push(int val) {// 单调栈的执行逻辑，每次让小的元素靠近栈顶// 添加元素的时候，类似于插入排序的思想。if(stack2.isEmpty()){stack2.push(val);}else{if(stack2.peek() > val){stack2.push(val);}else{Deque<Integer> stack3 = new LinkedList<>();while(!stack2.isEmpty() && stack2.peek() < val){stack3.push(stack2.pop());}stack2.push(val);while(!stack3.isEmpty()){stack2.push(stack3.pop());}}}stack1.push(val);}public void pop() {stack2.remove(stack1.pop());}public int top() {return stack1.peek();}// 直接取单调栈栈顶元素。public int getMin() {return stack2.peek();}
}
1.4 题解2：堆
java">class MinStack {Deque<Integer> deque;PriorityQueue<Integer> pq;public MinStack() {deque = new LinkedList<>();pq = new PriorityQueue<>();}public void push(int val) {deque.push(val);pq.offer(val);}public void pop() {int val = deque.pop();pq.remove(val);}public int top() {return deque.peek();}public int getMin() {int val = pq.poll();pq.offer(val);return val;}
}2. 力扣1472：设计浏览器历史记录
2.1 题目：
你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。
请你实现 BrowserHistory 类：
BrowserHistory(string homepage)，用homepage初始化浏览器类。void visit(string url)从当前页跳转访问url对应的页面 。执行此操作会把浏览历史前进的记录全部删除。string back(int steps)在浏览历史中后退steps步。如果你只能在浏览历史中后退至多x步且steps > x，那么你只后退x步。请返回后退 至多steps步以后的url。string forward(int steps)在浏览历史中前进steps步。如果你只能在浏览历史中前进至多x步且steps > x，那么你只前进x步。请返回前进 至多steps步以后的url。
示例：
输入： ["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"] [["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]] 输出： [null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]解释： BrowserHistory browserHistory = new BrowserHistory("leetcode.com"); browserHistory.visit("google.com"); // 你原本在浏览 "leetcode.com" 。访问 "google.com" browserHistory.visit("facebook.com"); // 你原本在浏览 "google.com" 。访问 "facebook.com" browserHistory.visit("youtube.com"); // 你原本在浏览 "facebook.com" 。访问 "youtube.com" browserHistory.back(1); // 你原本在浏览 "youtube.com" ，后退到 "facebook.com" 并返回 "facebook.com" browserHistory.back(1); // 你原本在浏览 "facebook.com" ，后退到 "google.com" 并返回 "google.com" browserHistory.forward(1); // 你原本在浏览 "google.com" ，前进到 "facebook.com" 并返回 "facebook.com" browserHistory.visit("linkedin.com"); // 你原本在浏览 "facebook.com" 。 访问 "linkedin.com" browserHistory.forward(2); // 你原本在浏览 "linkedin.com" ，你无法前进任何步数。 browserHistory.back(2); // 你原本在浏览 "linkedin.com" ，后退两步依次先到 "facebook.com" ，然后到 "google.com" ，并返回 "google.com" browserHistory.back(7); // 你原本在浏览 "google.com"， 你只能后退一步到 "leetcode.com" ，并返回 "leetcode.com"
提示：
1 <= homepage.length <= 201 <= url.length <= 201 <= steps <= 100homepage和url都只包含 '.' 或者小写英文字母。- 最多调用
5000次visit，back和forward函数。
2.2 思路：
设计题，编程语言翻译题目意思。
2.3 题解：
java">class BrowserHistory {List<String> list = new LinkedList<>();// i是指向当前页面的指针int i;public BrowserHistory(String homepage) {list.add(homepage);i = 0;}//如果当前页面就是最新页面，那么就新增页面// 否则将当前页面的前面的历史页面都删除，再新增页面public void visit(String url) {if(i == list.size() - 1){i++;list.add(url);}else{for(int j = list.size() - 1; j > i; j--){list.remove(j);}list.add(url);i++;}}// 回退失败的话就回退到第一个页面public String back(int steps) {i = i - steps;// 回退失败if(i < 0){i = 0;return list.get(0);}return list.get(i);}// 前进失败的话就前进到最新页面public String forward(int steps) {i += steps;if(i >= list.size()){i = list.size()-1;;return list.get(list.size()-1);}return list.get(i);}
}3. 力扣1381：设计一个支持增量操作的栈
3.1 题目：
请你设计一个支持对其元素进行增量操作的栈。
实现自定义栈类 CustomStack ：
CustomStack(int maxSize)：用maxSize初始化对象，maxSize是栈中最多能容纳的元素数量。void push(int x)：如果栈还未增长到maxSize，就将x添加到栈顶。int pop()：弹出栈顶元素，并返回栈顶的值，或栈为空时返回 -1 。void inc(int k, int val)：栈底的k个元素的值都增加val。如果栈中元素总数小于k，则栈中的所有元素都增加val。
示例：
输入： ["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"] [[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]] 输出： [null,null,null,2,null,null,null,null,null,103,202,201,-1] 解释： CustomStack stk = new CustomStack(3); // 栈是空的 [] stk.push(1); // 栈变为 [1] stk.push(2); // 栈变为 [1, 2] stk.pop(); // 返回 2 --> 返回栈顶值 2，栈变为 [1] stk.push(2); // 栈变为 [1, 2] stk.push(3); // 栈变为 [1, 2, 3] stk.push(4); // 栈仍然是 [1, 2, 3]，不能添加其他元素使栈大小变为 4 stk.increment(5, 100); // 栈变为 [101, 102, 103] stk.increment(2, 100); // 栈变为 [201, 202, 103] stk.pop(); // 返回 103 --> 返回栈顶值 103，栈变为 [201, 202] stk.pop(); // 返回 202 --> 返回栈顶值 202，栈变为 [201] stk.pop(); // 返回 201 --> 返回栈顶值 201，栈变为 [] stk.pop(); // 返回 -1 --> 栈为空，返回 -1
提示：
1 <= maxSize, x, k <= 10000 <= val <= 100- 每种方法
increment，push以及pop分别最多调用1000次
3.2 思路：
设计题，翻译题目意思。
3.3 题解：
java">class CustomStack {Deque<Integer> stack = new LinkedList<>();int maxsize;//记录栈中的最大个数int size;public CustomStack(int maxSize) {maxsize = maxSize;}public void push(int x) {if(size < maxsize){stack.push(x);size++;}}public int pop() {if(size == 0){return -1;}size--;return stack.pop();}public void increment(int k, int val) {// 栈中元素总数小于kif(size <= k){int n = size;while(n-- > 0){// 从栈顶删除元素，然后加入到新的栈stack.push(stack.pollLast() + val);}}else{int n = k;Deque<Integer> stack1 = new LinkedList<>();while(n-- > 0){stack1.push(stack.pollLast() + val);}while(!stack.isEmpty()){stack1.push(stack.pollLast());}stack = stack1;}}
}
