关于java栈类：Stack<>：
Java堆栈Stack类已经过时，Java官方推荐使用Deque替代Stack使用。Deque堆栈操作方法：push()、pop()、peek()。
Deque<T> stack = new ArrayDeque<>();
stack.push(数据);
T stack.peek();
T stack.pop();
队列
Queue<T> queue = new Queue<>();
boolean offer(E e);//将指定的元素插入此队列
E poll();//获取并移除此队列的头，如果此队列为空，则返回 null。
E peek();//获取但不移除此队列的头；如果此队列为空，则返回 null。
单调栈基本架构：
class Solution {
public boolean verifyPostorder(int[] postorder) {
Deque<Integer> stack = new ArrayDeque<>();
for(遍历数据列表)){
逻辑操作
while(!stack.isEmpty() && stack.peek() 大于或小于当前值){
stack.pop();
}
stack.push(当前值)；
}
}
}
42、接雨水-困难
题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
思路1:将每一列能存放的雨水加起来
- 每一列是否能存放的雨水由该列前后的最高柱子决定，如果前后最高柱子中较矮的柱子高度大于该列柱子高度，则该列存放的雨水等于较矮柱子高度减该列柱子的高度；如果小于等于该列柱子高度则该列无法存水。
- 可以使用双指针对其找前后最大值优化
代码1
class Solution {
public int trap(int[] height) {
if(height == null || height.length <= 2) return 0;
int len = height.length;
int left = 1, right = len -2;
int leftMax = height[0], rightMax = height[len-1];
int sum = 0;
while(left <= right){
leftMax = Math.max(leftMax, height[left-1]);
rightMax = Math.max(rightMax, height[right+1]);
if(leftMax <= rightMax){
if(leftMax > height[left]){
sum += leftMax - height[left];
}
left++;
}else{
if(rightMax > height[right]){
sum += rightMax - height[right];
}
right--;
}
}
return sum;
}
}
思路2:单调栈
如果当前柱子高度小于等于栈顶柱子高度，则该柱子入栈；如果大于，则计算当前柱子与前面所接的雨水，计算方法看代码
代码2
class Solution {
public int trap(int[] height) {
if(height == null || height.length <= 2) return 0;
int len = height.length, sum = 0;
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < len; i++){
while(!stack.empty() && height[stack.peek()] < height[i]){
//计算当前柱子与前面所接的雨水,将栈顶元素pop出来，计算当前柱子与新栈顶的柱子接的雨水，直到栈顶柱子
//大于等于当前柱子。
int top1 = stack.pop();
if(stack.empty()) break;
int top2 = stack.peek();
int distance = i - top2 - 1;
int h = Math.min(height[top2], height[i]) - height[top1];
sum += distance * h;
}
stack.push(i);
}
return sum;
}
}
71、简化路径-中等
题目
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，’//’）都被视为单个斜杠 ‘/’ 。 对于此问题，任何其他格式的点（例如，’…’）均被视为文件/目录名称。
请注意，返回的 规范路径 必须遵循下述格式：
始终以斜杠 ‘/’ 开头。
两个目录名之间必须只有一个斜杠 ‘/’ 。
最后一个目录名（如果存在）不能 以 ‘/’ 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘…’）。
返回简化后得到的 规范路径 。
思路：使用String的split方法一“/”分开，
代码
class Solution {
public String simplifyPath(String path) {
if(path == null || path.length() == 0) return "/";
//去掉重复“ / ”，也可以不去掉，在pathArray中重复的“ / ”是空格。
String removed = remove(path);
String[] pathArray = removed.split("/");
int len = pathArray.length;
String[] pathArray2 = new String[len+1];
int point = 0;//栈顶指针
for(int i = 1; i < len; i++){
if(!pathArray[i].equals(".") && !pathArray[i].equals("..")){
pathArray2[point] = pathArray[i];
point++;
}
if(pathArray[i].equals("..") && point > 0){
point--;
}
}
if(point == 0) return "/";
String result = "";
for(int i = 0; i < point; i++){
result += "/";
result += pathArray2[i];
}
return result;
}
public String remove(String str){
StringBuffer result = new StringBuffer();
int len = str.length();
for(int i = 0; i < len; i++){
result.append(str.charAt(i));
if(str.charAt(i) == '/'){
while(i < len - 1 && str.charAt(i) == str.charAt(i+1)) i++;
}
}
return result.toString();
}
}
84、柱状图的最大矩形-困难
题目
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
思路1:暴力算法，看那一根柱子作为矩形高能形成的矩形面积最大
- 超出时间限制，无法AC
- 时间复杂度：O(N^2)
代码1
class Solution {
public int largestRectangleArea(int[] heights) {
int maxArea = 0;
if(heights == null || heights.length == 0) return 0;
int len = heights.length;
for(int i = 0; i < len; i++){
int maxTemp = 0;
for(int j = 0; j < len; j++){
if(heights[j] >= heights[i]){
maxTemp += heights[i];
}
if(heights[j] < heights[i] || j == len - 1){
maxArea = Math.max(maxArea, maxTemp);
maxTemp = 0;
}
}
}
return maxArea;
}
}
思路2:单调栈
单调栈：栈里面的元素是有序的，单调递增或递减。
代码2
class Solution {
public int largestRectangleArea(int[] heights) {
int maxArea = 0;
if(heights == null || heights.length == 0) return 0;
int len = heights.length;
Deque<Integer> stack = new ArrayDeque<>();
//因为是单调栈，所以栈中所有元素的左边界值都是当前位置的前一个位置
//但是当与前一个位置元素相等时，该元素左边界值显然并不等于前面一个的位置
//但这并不影响算该高度的矩形面积。
for(int i = 0; i < len; i++){
//如果小于栈顶元素，就知道了栈顶元素及后面所有大于当前元素的右边第一个小于他们的值的位置
while(!stack.isEmpty() && heights[i] < heights[stack.peek()]){
int top1Index = stack.pop();
int top2Index = stack.isEmpty() ? -1 : stack.peek();
int area = (i - top2Index - 1) * heights[top1Index];
maxArea = Math.max(maxArea, area);
}
// if(stack.isEmpty() || heights[i] > heights[stack.peek()])
stack.push(i);
}
//最后栈如果不为空，则栈中所有元素的右边界位置为len
while(!stack.isEmpty()){
int top1Index = stack.pop();
int top2Index = stack.isEmpty() ? -1 : stack.peek();
int area = (len - top2Index - 1) * heights[top1Index];
maxArea = Math.max(maxArea, area);
}
return maxArea;
}
}
85、最大矩形-困难
题目
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
思路：84题的变形
一行中每个元素与当前列前面连续1的个数就是84题中的高度。如果当前元素为0，显然与前面组成连续1的长度就为0.
由于是连续1的个数算作高度，所以必须每一行更新高度数组，再将高度数组给84题找最大矩形面积。
- 时间复杂度：O(mn)
代码
class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix == null || matrix.length == 0) return 0;
int maxArea = 0;
int rowLen = matrix[0].length;
int heights[] = new int[rowLen];
for(int i = 0; i < matrix.length; i++){
//新的一行更新柱子高度，如果当前值为0，则当前列的柱子高度就直接变为0，否则高度+1.
for(int j = 0; j < rowLen; j++){
if(matrix[i][j] != '0'){
heights[j]++;
}else{
heights[j] = 0;
}
}
//将新的柱子高度数组传给函数求能组成的最大矩形面积
maxArea = Math.max(largestRectangleArea(heights), maxArea);
}
return maxArea;
}
//第84题
public int largestRectangleArea(int[] heights) {
int maxArea = 0;
if(heights == null || heights.length == 0) return 0;
int len = heights.length;
Deque<Integer> stack = new ArrayDeque<>();
for(int i = 0; i < len; i++){
while(!stack.isEmpty() && heights[i] < heights[stack.peek()]){
int top1Index = stack.pop();
int top2Index = stack.isEmpty() ? -1 : stack.peek();
int area = (i - top2Index - 1) * heights[top1Index];
maxArea = Math.max(maxArea, area);
}
// if(stack.isEmpty() || heights[i] > heights[stack.peek()])
stack.push(i);
}
while(!stack.isEmpty()){
int top1Index = stack.pop();
int top2Index = stack.isEmpty() ? -1 : stack.peek();
int area = (len - top2Index - 1) * heights[top1Index];
maxArea = Math.max(maxArea, area);
}
return maxArea;
}
155、最小栈-简单
题目
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
思路:ArrayList实现，minIndex保存最小值下标
- pop时需要考虑栈顶位置的值是否就是最小值的位置，如果是则需要重新更新minIndex；
代码
class MinStack {
private List<Integer> list;
private int size;
private int minIndex;
/** initialize your data structure here. */
public MinStack() {
this.list = new ArrayList<>();
this.size = 0;
this.minIndex = -1;
}
public void push(int x) {
//更新minIndex
if(minIndex != -1){
if(list.get(minIndex) > x){
minIndex = size;
}
}else{
this.minIndex = 0;
}
list.add(x);
size++;
}
public void pop() {
if(size > 0){
if(size == 1) minIndex = -1;//如果只有一个元素，单独更新minIndex=-1
//从新遍历list更新minIndex
if(minIndex == size-1){
minIndex = 0;
for(int i = 0; i < size - 1; i++){
if(list.get(minIndex) > list.get(i)){
minIndex = i;
}
}
}
list.remove(--size);
}
}
public int top() {
return list.get(size-1);
}
public int getMin() {
return list.get(minIndex);
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
思路:ListNode链表实现，min作为结点的属性保存最小值
代码
class MinStack {
private Node head;
public void push(int x) {
if(head == null)
head = new Node(x, x);
else
head = new Node(x, Math.min(x, head.min), head);
}
public void pop() {
head = head.next;
}
public int top() {
return head.val;
}
public int getMin() {
return head.min;
}
private class Node {
int val;
int min;
Node next;
private Node(int val, int min) {
this(val, min, null);
}
private Node(int val, int min, Node next) {
this.val = val;
this.min = min;
this.next = next;
}
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
42、用队列实现栈-简单
题目
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false
思路
让queue2为辅助栈，入栈元素先存入queue2中，再将queue1的元素依次出队进入queue2，最后将空的队列queue1与queue2交换，让queue1成为存放元素的队列，queue2继续为空的辅助队列。
代码
class MyStack {
private Queue<Integer> queue1;
private Queue<Integer> queue2;
/** Initialize your data structure here. */
public MyStack() {
queue1 = new ArrayDeque<>();
queue2 = new ArrayDeque<>();
}
/** Push element x onto stack. */
public void push(int x) {
queue2.offer(x);
while(!queue1.isEmpty()){
queue2.offer(queue1.poll());
}
Queue<Integer> temp = null;
temp = queue1;
queue1 = queue2;
queue2 = temp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue1.poll();
}
/** Get the top element. */
public int top() {
return queue1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
42、用栈实现队列-简单
题目
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false
思路
stack1作为存队列元素栈，push时先将stack1全部出栈进stack2，再将元素push进stack2；pop和peek时先将stack2全部出栈进stack1，再将stack1顶部元素pop和peek。判断空时必须两个栈均空队列才算空。
class MyQueue {
private Deque<Integer> stack1;
private Deque<Integer> stack2;
/** Initialize your data structure here. */
public MyQueue() {
stack1 = new ArrayDeque<>();
stack2 = new ArrayDeque<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
stack2.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
while(!stack2.isEmpty()){
stack1.push(stack2.pop());
}
return stack1.pop();
}
/** Get the front element. */
public int peek() {
while(!stack2.isEmpty()){
stack1.push(stack2.pop());
}
return stack1.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stack1.isEmpty() && stack2.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();
*/
402、移除K位数字-中等
题目
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
思路：单调栈
- 由于要保持原有相对位置不变，如果一个数的后面那个数比自己大，则这个数就不能移除，因为移除了这一位就变成后面那个数了，显然就变大了，因此可以用单调递增栈的思想来解决。
代码
class Solution {
public String removeKdigits(String num, int k) {
if( k == 0) return num;
if(num.length() == k) return "0";
StringBuffer stack = new StringBuffer();
int len = num.length();
for(int i = 0; i < len; i++){
char ch = num.charAt(i);
while(k > 0 && stack.length() > 0 && num.charAt(i) < stack.charAt(stack.length()-1) ){
stack.setLength(stack.length()-1);
k--;
}
if(num.charAt(i) == '0' && stack.length() == 0) continue;
stack.append(num.charAt(i));
}
String result = stack.substring(0, stack.length()-k);
return "".equals( result ) ? "0" : result;
}
}
316、去除重复字母-困难
题目
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
思路：单调栈
在402题中，如果当前位置的数大于下一个位置的数即可移除当前位置的数使最后的数最小。这题一样的思想，也是保持原相对位置移除某些字母让最后的字典序最小，402是移除任意K位，而本题只能移除重复的字母，所以其实只是单调栈的判断条件不一样了而已，如果当前位置当前位置的字符大于下一个位置的字符的话想要移除当前字符还得属于重复字符。其他细节看代码
代码
class Solution {
public String removeDuplicateLetters(String s) {
//用StringBuffer模仿栈
StringBuffer stack = new StringBuffer();
//记录字符的出现次数，也可以使用数组下标位字符，值为次数保存：aray[300]
HashMap<Character,Integer> map = new HashMap<>();
//判断字符在前面是否已经含有，也可以专门定义一个数组保存每个字符是否已经出现：array[26]
HashSet<Character> set = new HashSet<>();
int len = s.length();
//记录每个字符出现的次数
for(int i = 0; i < len; i++){
char ch = s.charAt(i);
int count = 1;
if( map.containsKey(ch) ){
count = map.get(ch);
count++;
}
map.put(ch, count);
}
// for(char key:map.keySet()){
// System.out.println("key:"+key+",value:"+map.get(key));
// }
for(int i = 0; i < len; i++){
char ch1 = s.charAt(i);
//首先判断当前字符前面是否已经拥有，如果前面已经有了就可以直接丢弃该字符
if( !set.contains(ch1) ){
//单调栈思想：只不过除了不满足单调关系外多了个条件该元素必须为重复元素才出栈，不然不能出栈。
while( stack.length() > 0 && map.get( stack.charAt(stack.length()-1) ) > 1 && ch1 < stack.charAt(stack.length()-1) ){
//1、栈顶元素出栈2、判断字符是否已经含有的set也相应删除栈顶字符3、同时还要更新记录字符的出现次数。
char ch2 = stack.charAt(stack.length()-1);
set.remove( ch2 );
int count = map.get(ch2) - 1;
map.put(ch2, count);
stack.setLength(stack.length()-1);
}
stack.append(ch1);
set.add(ch1);//加入到集合，用来快速判断元素是否已经含有
}else{
//直接丢弃后更新记录字符的出现次数。
int count = map.get(ch1) - 1;
map.put(ch1, count);
}
// System.out.println("stack:"+stack);
}
return stack.toString();
}
}