栈：先入后出
使用java代码实现一个栈
public class Stack<T> {
List<T> data;
public Stack() {
// 初始化
data = new ArrayList<T>();
}
public void push(T t) {
data.add(t);
}
public void pop() {
if (data.size() <= 0) {
return 0;
}
data.remove(data.size() - 1);
}
public T Top() {
return data.get(data.size() - 1);
}
}
跑个Junit
@Test
public void test() {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.pop();
System.out.println(stack.Top());
}
OK 输出3，断点显示 [1,2,3] 正确
其实java.util中有Stack的实现 Stack<E> stack = new Stack<>();
题目：设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) -- 将元素 x 推入栈中。
- pop() -- 删除栈顶的元素。
- top() -- 获取栈顶元素。
- getMin() -- 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
class MinStack {
List<Integer> data;
/** initialize your data structure here. */
public MinStack() {
data = new ArrayList<>();
}
public void push(int x) {
data.add(x);
}
public void pop() {
if (data.size() > 0) {
data.remove(data.size() - 1);
}
}
public int top() {
return data.get(data.size() - 1);
}
public int getMin() {
// 排序算法
List<Integer> sortData = new ArrayList<>();
// sortData = data; 这种写法是错误的，此时sortData指向的仍然是data的地址
sortData.addAll(data);
Collections.sort(sortData);
return sortData.get(0);
}
}
我这种写法有些low,而且深入Collections源码，最后发现其排序的方法是Arrays.java里的mergeSort方法：
private static void mergeSort(Object[] src,
Object[] dest,
int low,
int high,
int off) {
int length = high - low;
// Insertion sort on smallest arrays
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
// Recursively sort halves of dest into src
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);
// If list is already sorted, just copy from src to dest. This is an
// optimization that results in faster sorts for nearly ordered lists.
if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}
// Merge sorted halves (now in src) into dest
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}
时间复杂度绝对超出常数了，能力不行只能学习。
通过借鉴了别的大佬的思路，大致有两种：一、借用辅助栈；二、不借用辅助栈。两种思路都很6，还有一种是直接改底层使用链表实现。
使用辅助栈
public class MinStack {
Stack<Integer> stack;
Stack<Integer> helper;
public MinStack() {
stack = new Stack<>();
helper = new Stack<>();
}
public void push(Integer x) {
// 当辅助栈为空或者入栈元素为最小元素入辅助栈
if (helper.isEmpty() || (x <= helper.peek())) {
helper.push(x);
}
stack.push(x);
}
public void pop() {
// 当辅助栈非空 同时 stack的栈顶元素为最小元素
if (!helper.isEmpty() && (stack.peek() == helper.peek())) {
helper.pop();
}
stack.pop();
}
public int top(){
return stack.peek();
}
public int getMin(){
return helper.peek();
}
}
不用辅助栈的思路，其实跟用辅助栈差不多。 就是使用一个标志符记录min，每次入栈的时候，如果是最小值则把之前的最小值入栈。
class MinStack {
Stack<Integer> stack;
// Stack<Integer> helper;
// 用一个min记录最小值
Integer min;
public MinStack() {
stack = new Stack<>();
// helper = new Stack<>();
// 存最大值
min = Integer.MAX_VALUE;
}
public void push(Integer x) {
// 当辅助栈为空或者入栈元素为最小元素入辅助栈
// if (helper.isEmpty() || (x <= helper.peek())) {
// helper.push(x);
// }
// 如果入栈的值小于最小值，则最小值入栈并记录最小值
if (x <= min) {
stack.push(min);
min = x;
}
stack.push(x);
}
public void pop() {
// 当辅助栈非空 同时 stack的栈顶元素为最小元素
// if (!helper.isEmpty() && (stack.peek() == helper.peek())) {
// helper.pop();
// }
// 这里就很巧妙，在判读里先将出栈元素出栈，如果出栈的元素等于min，则再把记录的min出栈
if (stack.pop() == min) {
min = stack.pop();
}
// stack.pop();
}
public int top(){
return stack.peek();
}
public int getMin(){
// return helper.peek();
return min;
}
当我们没有思路，或写完之后。完全可以去看看题解，我们会突然感觉豁然开朗或者多出很多新思路。。。
这里我就参考了这个题解
https://leetcode-cn.com/problems/min-stack/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/
题目：有效的括号
- 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
- 有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
示例：
输入: "{[]}"
输出: true
输入: "{(}"
输出: false
/**
* @author weichen
* @description: 有效的括号
* @create 2020-04-07 14:08
*/
public class ValidParentheses {
class Solution {
// 使用HashMap做预先存储
HashMap<Character, Character> map = new HashMap<Character, Character>() {
{
put(']','[');
put('}','{');
put(')','(');
}
};
public boolean isValid(String s){
// new一个新的栈
Stack<Character> stack = new Stack<>();
// 遍历字符串
for (int i = 0; i < s.length(); i++) {
// 因为题目说只有{}[](),所以不考虑其他字符和空格,预先记录当前字符
char c = s.charAt(i);
if (map.containsKey(c)) {
// 如果是结尾符号,判断stack是否是空，是空压入一个特殊字符，否则出栈，防止stack为空是pop抛错
char temp = stack.empty() ? '?' : stack.pop();
// 如果结尾和开头不同，返回false
if (temp != map.get(c)) return false;
} else {
// 开头字符全入栈
stack.push(s.charAt(i));
}
}
return stack.empty();
}
}
}
其他的题解，要不是不使用HashMap，全使用if-else，要不是不使用栈，直接数组手写。追求性能极致，牛逼！我就算了，我只最求解决思路。。。
还有看题解 有的使用stack.empty判空，有的使用isEmpty判空。我看了下源码，奥，其实empty和isEmpty是一个意思，因为Stack在java中继承了Vector向量类。isEmpty是Vector里的方法，empty是Stack里面自写的。判断方法都一样。
// 判断这个是不是 0
elementCount == 0
题目: 每日温度
根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
这道题我感觉翻译的没有那个味，还是英文原题更让人理解些
Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].
Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].
是不是更好理解了
@Component
public class DailyTmperatures {
Solution solution;
public DailyTmperatures() {
solution = new Solution();
}
class Solution {
public int[] dailyTemperatures(int[] T) {
// 基本的解题思路，直接for循环再套一个for循环
// 时间复杂度O(n^2)
int[] result = new int[T.length];
for (int i = 0; i < T.length; i++) {
int temp = T[i];
int count = 0;
boolean flag = false;
for (int j = i+1; j < T.length ; j++) {
count++;
if (temp < T[j]) {
result[i] = count;
flag = true;
break;
}
}
if (!flag) result[i] = 0;
}
return result;
}
}
}
上面的是强势破解法，嗯，很low。。。至少解决了，我去膜拜下大佬的解决方案。
// 用递减栈来解决该问题
class solucation2 {
// 栈 用来存储下标，注意 已知下标的话，必可知元素
Stack<Integer> stack;
// 结果集，用来存储隔离天数
int [] postions;
public int[] dailyTemperatures(int[] T) {
stack = new Stack<>();
postions = new int [T.length];
// 遍历数组
for (int i = 0; i < T.length; i++) {
// 这里理论上将就是遍历栈，来检测是否还有元素小于当前元素的，及升温
while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
// 隔离天数 为当前下表减去栈顶下表计算出来的
postions[stack.peek()] = i - stack.peek();
// 出栈
stack.pop();
}
// 如果遍历完栈，记得当前下表入栈
stack.push(i);
}
return postions;
}
}
还是不懂可以去看下leetcode的题解，里面还有完美的动画展示。。。
题目： 逆波兰表达式求值
根据逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9
这题挺简单的，只要去了解下逆波兰表示法是啥意思。
百度一下：
逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。
class Solution {
// 这里可以不用哈希表，直接catch字符串就行
HashMap<String , Integer> map = new HashMap() {
{
put("+", 1);
put("-", 2);
put("*", 3);
put("/", 4);
}
};
Stack<Integer> stack;
public int evalRPN(String[] tokens) {
stack = new Stack<>();
int result = 0;
// 遍历数组
for (int i = 0; i < tokens.length; i++) {
// 运算符switch
if (!stack.isEmpty() && map.containsKey(tokens[i])) {
Integer first = stack.pop();
Integer second = stack.pop();
switch (map.get(tokens[i])) {
case 1:
result = second + first;
stack.push(result);
break;
case 2:
result = second - first;
stack.push(result);
break;
case 3:
result = second * first;
stack.push(result);
break;
case 4:
result = second / first;
stack.push(result);
break;
default:
break;
}
} else {
// 否则直接入栈
stack.push(Integer.valueOf(tokens[i]));
}
}
return stack.pop();
}
}
