快速建设企业门户网站,南宁seo推广,广州市开发区建设局官方网站,包装设计是什么栈
特点#xff1a; 先进后出#xff0c;后进先出
适合#xff1a; 相当于一个暂存的地方#xff0c;方便回来找
特#xff1a; 单调栈——需要找到左边或者右边第一个比当前位置数大或者小的数字
数据类型
LinkedListT stack new LinkedList();
ad…栈
特点 先进后出后进先出
适合 相当于一个暂存的地方方便回来找
特 单调栈——需要找到左边或者右边第一个比当前位置数大或者小的数字
数据类型
LinkedListT stack new LinkedList();
addFirstpush;removeFirstpop;peek// 面向接口编程封装性更好
DequeT stack new ArrayDeque();
addLastpush;pollLastpop;peekLast1.有效的括号20简单
class Solution {public boolean isValid(String s) {// 使用Java中的LinkedList创建栈遍历s如果和栈顶元素匹配则弹出如果不匹配则压入遍历结束后如果列表为空说明字符串是有效的反之无效// 注意Java中定义集合如果集合元素是基本数据类型要使用他们的包装类String不是数组没有索引// 改进使用哈希map将括号存起来不用这么多if条件// 1. 进行一些特殊情况的判断int len s.length();// 如果字符串长度是奇数说明不是有效字符串if (len % 2 ! 0) {return false;}// 2. 定义栈_Java中定义集合如果集合元素是基本数据类型要使用他们的包装类LinkedListCharacter stack new LinkedList();// 3. 开始遍历字符串for (int i 0; i len; i) {if (stack.size() 0 || s.charAt(i) ( || s.charAt(i) { || s.charAt(i) [) {stack.addFirst(s.charAt(i));} else {char temp stack.removeFirst();if ((temp ( s.charAt(i) )) || (temp { s.charAt(i) }) || (temp [ s.charAt(i) ])) {continue;} else {return false;}}}if (stack.size() 0) {return true;}return false;}
}简单题补充
1047删除字符串中的所有相邻重复项]
class Solution {public String removeDuplicates(String s) {// 思路遍历字符串s将字符串中的字符压入栈中最后将栈中元素弹出并翻转得到最终字符串// 压栈栈为空或栈顶元素与遍历到的元素不相等// 出栈栈顶元素与遍历到的元素相等// 1. 定义一个栈DequeCharacter stack new ArrayDeque();// 2. 遍历for (int i 0; i s.length(); i) {if (stack.isEmpty()) {stack.addLast(s.charAt(i));continue;}if (stack.peekLast() s.charAt(i)) {stack.pollLast();} else {stack.addLast(s.charAt(i));}}// 3. 定义结果字符串为了方便翻转定义StringBuilderStringBuilder result new StringBuilder();while (!stack.isEmpty()) {result.append(stack.pollLast());}return result.reverse().toString();}
}150. 逆波兰表达式求值
class Solution {public int evalRPN(String[] tokens) {// 思路定义一个栈如果是数字压入栈中如果是运算符弹出两个数字计算之后将结果压入栈中最后遍历结束栈中存在的最后一个值就是整个表达式的计算值// 注意计算的时候弹出来的数计算要反过来DequeInteger stack new ArrayDeque();int n tokens.length;for (int i 0; i n; i) {String s tokens[i];if (s.equals()) {int a stack.pollLast();int b stack.pollLast();stack.addLast(b a);System.out.println( stack.peekLast());} else if (s.equals(-)) {int a stack.pollLast();int b stack.pollLast();stack.addLast(b - a);} else if (s.equals(*)) {int a stack.pollLast();int b stack.pollLast();stack.addLast(b * a);} else if (s.equals(/)) {int a stack.pollLast();int b stack.pollLast();stack.addLast(b / a);System.out.println(/ stack.peekLast());} else {stack.addLast(Integer.parseInt(s));System.out.println(stack.peekLast());}}return stack.pollLast();}
}2.最小栈155中等
特点辅助栈的使用
// class MinStack {
// public int minValue; // 记录最小值
// public LinkedListInteger stack;// public MinStack() {
// minValue Integer.MAX_VALUE;
// stack new LinkedList();
// }// public void push(int val) {
// if (val minValue) {
// minValue val;
// }
// stack.addFirst(val);
// }// public void pop() {
// int temp stack.removeFirst();
// // 如果没有弹出最小元素
// if (temp ! minValue) {
// return;
// } else {
// // 如果弹出了最小元素
// minValue Integer.MAX_VALUE;
// for (int x: stack) {
// if (x minValue) {
// minValue x;
// }
// }
// }
// }// public int top() {
// int temp stack.removeFirst();
// stack.addFirst(temp);
// return temp;
// }// public int getMin() {
// return minValue;
// }
// }// 使用辅助栈也就是最小栈里面一致存放的是当前最小值压入新元素最小栈比较当前最小值和当前最小元素插入最小
class MinStack {LinkedListInteger xStack;LinkedListInteger minStack;public MinStack() {xStack new LinkedList();minStack new LinkedList();minStack.push(Integer.MAX_VALUE);}public void push(int val) {xStack.push(val);minStack.push(Math.min(val, minStack.peek()));}public void pop() {xStack.pop();minStack.pop();}public int top() {return xStack.peek();}public int getMin() {return minStack.peek();}
}3.每日温度739中等
单调栈的直接使用
// class Solution {
// public int[] dailyTemperatures(int[] temperatures) {
// // 思路单调栈如果遍历到当前元素小于栈顶元素压栈如果大于不断弹出
// LinkedListInteger indexStack new LinkedList();
// int len temperatures.length;
// int[] ans new int[len];
// // 遍历温度数组
// for (int i 0; i len; i) {
// // 如果栈是空的
// if (indexStack.isEmpty()) {
// indexStack.push(i);
// } else {
// // 不为空就要看栈顶元素和当前温度的大小
// if (temperatures[i] temperatures[indexStack.peek()]) {
// indexStack.push(i);
// } else {
// while (! indexStack.isEmpty()) {
// if (temperatures[i] temperatures[indexStack.peek()]) {
// int temp indexStack.pop();
// ans[temp] i - temp;
// } else {
// break;
// }
// }
// indexStack.push(i);
// }
// }
// }
// return ans;
// }
// }// 简化
class Solution {public int[] dailyTemperatures(int[] temperatures) {// 思路单调栈如果遍历到当前元素小于栈顶元素压栈如果大于不断弹出LinkedListInteger indexStack new LinkedList();int len temperatures.length;int[] ans new int[len];// 遍历温度数组for (int i 0; i len; i) {while (! indexStack.isEmpty()) {if (temperatures[i] temperatures[indexStack.peek()]) {int temp indexStack.pop();ans[temp] i - temp;} else {break;}}indexStack.push(i);}return ans;}
}4.柱状图中最大的矩形84困难
单调栈的反复使用
class Solution {public int largestRectangleArea(int[] heights) {// 思路遍历每根柱子找到左右两边第一个比它矮的面积为(右-左)*min(高度最小)int n heights.length;// 定义左右两个数组分别保存左边和右边第一个比该位置小的下标int[] l new int[n];int[] r new int[n];// 初始填充Arrays.fill(l, -1);Arrays.fill(r, n);// 定义栈——辅助寻找第一个小于的元素DequeInteger stack new ArrayDeque();// 从头到尾遍历找到右边第一个小于该位置的下标for (int i 0; i n; i) {while (! stack.isEmpty() heights[stack.peekLast()] heights[i]) {r[stack.pollLast()] i;}stack.addLast(i);}// 从尾遍历到头找到左边第一个不小于该位置的小标stack.clear();for (int i n - 1; i 0; i--) {while (!stack.isEmpty() heights[stack.peekLast()] heights[i]) {l[stack.pollLast()] i;}stack.addLast(i);}// 开始计算面积int maxVal 0;for (int i 0; i n; i) {maxVal Math.max(maxVal, heights[i] * (r[i] - l[i] - 1));}return maxVal;}
}[未完待续……]
总结 定义栈、三个栈的基本操作
单调栈加辅助空间
