一、数据结构与算法
前面的没记录就跳过吧
(一) 单调栈
Q1. 商品折扣后的最终价格
给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。
商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，如果没有满足条件的 j ，你将没有任何折扣。
请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。
示例 1：
输入：prices = [8,4,6,2,3]
输出：[4,2,4,2,3]
解释：
商品 0 的价格为 price[0]=8 ，你将得到 prices[1]=4 的折扣，所以最终价格为 8 – 4 = 4 。
商品 1 的价格为 price[1]=4 ，你将得到 prices[3]=2 的折扣，所以最终价格为 4 – 2 = 2 。
商品 2 的价格为 price[2]=6 ，你将得到 prices[3]=2 的折扣，所以最终价格为 6 – 2 = 4 。
商品 3 和 4 都没有折扣
示例 2：
输入：prices = [1,2,3,4,5] 输出：[1,2,3,4,5] 解释：在这个例子中，所有商品都没有折扣。
示例 3：
输入：prices = [10,1,1,6] 输出：[9,0,1,6]
提示：
1 <= prices.length <= 5001 <= prices[i] <= 10^3
解析：第一眼想到双重循环暴力解，不过这里需要用到单调栈。先遍历，栈里存“待打折”的商品序号，然后是相关操作
class Solution {
public int[] finalPrices(int[] prices) {
Deque<Integer> queue = new ArrayDeque<>();//记录待打折或无折扣商品序号
for(int i = 0;i<prices.length;i++){
while(queue.size()>0 && prices[i]<=prices[queue.getLast()]){
prices[queue.getLast()] -= prices[i];//原地操作更新打折后的值
queue.pollLast();//弹出栈顶商品序号
}
queue.addLast(i);//当前商品序号入栈
}
return prices;
}
}Q2. 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60] 输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90] 输出: [1,1,0]
提示：
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
解析：类似上一题操作，还是单调栈存待计算的天数，while循环操作
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n=temperatures.length;
int[] answer=new int[n];
Deque<Integer> stack=new ArrayDeque();
for(int i=0;i<n;i++){
while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){
answer[stack.peek()]=i-stack.peek();
stack.pop();
}
stack.push(i);
}
return answer;
}
}Q3. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4] 输出： 4
提示：
1 <= heights.length <=1050 <= heights[i] <= 104
解析：基本思路就是找一个数字右边出现的第一个比他小的数字或者直到数组边界，构成矩形然后计算宽乘以高，难点就是计算面积涉及一些边界的判断。
class Solution {
public int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>();
int n = heights.length;
int result = 0;
for (int i = 0; i <= n; i++) {
// 当前高度，遍历到n时高度为0，确保栈中所有元素都被弹出计算
int h = (i == n) ? 0 : heights[i];/*这里i=n的思路做题时一直没想到，看了解析才意识到作用，先记住吧*/
while (!stack.isEmpty() && h < heights[stack.peek()]) {
int height = heights[stack.pop()];
int left = stack.isEmpty() ? 0 : stack.peek() + 1;//左边界
int width = i - left;
result = Math.max(result, height * width);
}
stack.push(i);
}
return result;
}
}(二) 队列
Q1. 无法吃午餐的学生数量
学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮：
- 如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。
- 否则，这名学生会 放弃这个三明治 并回到队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。
给你两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 i 个三明治的类型（i = 0 是栈的顶部）， students[j] 是初始队列里第 j 名学生对三明治的喜好（j = 0 是队列的最开始位置）。请你返回无法吃午餐的学生数量。
示例 1：
输入：students = [1,1,0,0], sandwiches = [0,1,0,1]
输出：0
解释：
– 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,0,0,1]。
– 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,0,1,1]。
– 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [0,1,1]，三明治栈为 sandwiches = [1,0,1]。
– 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,1,0]。
– 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1,0]，三明治栈为 sandwiches = [0,1]。
– 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,1]。
– 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1]，三明治栈为 sandwiches = [1]。
– 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = []，三明治栈为 sandwiches = []。
所以所有学生都有三明治吃。
示例 2：
输入：students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1] 输出：3
提示：
1 <= students.length, sandwiches.length <= 100students.length == sandwiches.lengthsandwiches[i]要么是0，要么是1。students[i]要么是0，要么是1。
解析：第一想法就是new一个特别长的数组，给students数组填进去，然后用头索引和尾索引来操作暴力模拟队列，如下
class Solution {
public int countStudents(int[] students, int[] sandwiches) {
int j=0;
int n=students.length;
int nn=students.length;//超绝随意命名
int[] a=new int[10000];
for(int i=0;i<n;i++){
a[i]=students[i];
}
int i=0;
//添加一个计数器，记录当前轮次检查了多少学生
int checkedCount = 0;
while(j != sandwiches.length){
if(i >= nn&&checkedCount == (n - i)){
// 检查是否已经遍历了所有学生
break;
}
if(a[i]==sandwiches[j]){
j++;
i++;
checkedCount = 0; // 重置计数器
}else{
a[n++]=a[i];
i++;
checkedCount++; // 计数器增加
}
}
int result;
return result=n-i;
}
}然而看官解，本题只需要返回无法吃到三明治的人数，三明治顺序固定而学生可以无限排队，那么只需要把所有学生中喜欢1或0的总数，和当前三明治的种类来判断就好了。（唉唉我怎么就没想到呢）
class Solution {
public int countStudents(int[] students, int[] sandwiches) {
int s1 = Arrays.stream(students).sum();//计算students的和，相当于喜欢1的人数
int s0 = students.length - s1;//喜欢0的人数
for (int i = 0; i < sandwiches.length; i++) {
if (sandwiches[i] == 0 && s0 > 0) {
s0--;
} else if (sandwiches[i] == 1 && s1 > 0) {
s1--;
} else {
break;//都不喜欢就结束
}
}
return s0 + s1;
}
}Q2. 买票需要的时间
有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。
给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。
每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到 队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。
返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。
示例 1：
输入：tickets = [2,3,2], k = 2
输出：6
解释：
- 队伍一开始为 [2,3,2]，第 k 个人以下划线标识。
- 在最前面的人买完票后，队伍在第 1 秒变成 [3,2,1]。
- 继续这个过程，队伍在第 2 秒变为[2,1,2]。
- 继续这个过程，队伍在第 3 秒变为[1,2,1]。
- 继续这个过程，队伍在第 4 秒变为[2,1]。
- 继续这个过程，队伍在第 5 秒变为[1,1]。
- 继续这个过程，队伍在第 6 秒变为[1]。第 k 个人完成买票，所以返回 6。
示例 2：
输入：tickets = [5,1,1,1], k = 0
输出：8
解释：
- 队伍一开始为 [5,1,1,1]，第 k 个人以下划线标识。
- 在最前面的人买完票后，队伍在第 1 秒变成 [1,1,1,4]。
- 继续这个过程 3 秒，队伍在第 4 秒变为[4]。
- 继续这个过程 4 秒，队伍在第 8 秒变为[]。第 k 个人完成买票，所以返回 8。
提示：
n == tickets.length1 <= n <= 1001 <= tickets[i] <= 1000 <= k < n
解析：第一方法还是和上一题类似可以用数组模拟队列不再赘述。分析题目不难看出，买票轮流来，直到第k个人买完时已经完整经过k-1轮再加上k前面的人，也就是说此时k前面的人应该也都买了k次，k后面的人也都买了k-1次，在此基础上额外判断一下欲买票数比tickets[k]少的操作一下然后全加起来即可。
class Solution {
public int timeRequiredToBuy(int[] tickets, int k) {
int n = tickets.length;
int t = tickets[k];
int result = 0;
for (int i = 0; i < k; i++) {
result += Math.min(tickets[i], t);
}//前面
for (int i = k + 1; i < n; i++) {
result += Math.min(tickets[i], t - 1);
}//后面
result += t;//自己
return result;
}
}Q3. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入： [“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”] [[], [1], [2], [], [], []] 输出：
[null, null, null, 1, 1, false]
解释： MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); //return 1, queue is [2]
myQueue.empty(); // return false
提示：
1 <= x <= 9- 最多调用
100次push、pop、peek和empty - 假设所有操作都是有效的 （例如，一个空的队列不会调用
pop或者peek操作）
进阶：
- 你能否实现每个操作均摊时间复杂度为
O(1)的队列？换句话说，执行n个操作的总时间复杂度为O(n)，即使其中一个操作可能花费较长时间。
解析：对于java，本身就有双端队列Deque，直接deque.addLast；deque.removeFirst等即可。如果按照题意用两个栈，就需要一个in栈放接受的新数据，一个out栈放待输出的数据。官解：
class MyQueue {
Deque<Integer> inStack;
Deque<Integer> outStack;
public MyQueue() {
inStack = new ArrayDeque<Integer>();
outStack = new ArrayDeque<Integer>();
}
public void push(int x) {
inStack.push(x);//直接push
}
public int pop() {
if (outStack.isEmpty()) {
in2out();//如果out为空，调用把in倒进out的方法
}
return outStack.pop();
}
public int peek() {
if (outStack.isEmpty()) {
in2out();
}
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
private void in2out() {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());/*循环把in栈全倒过来放进out栈，这样in的最底位在out里就是最高位，实现先进先出*/
}
}
}(三) 堆
Q1. 最后一块石头的重量
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
示例：
输入：[2,7,4,1,8,1] 输出：1 解释： 先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]， 再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]， 接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]， 最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
提示：
1 <= stones.length <= 301 <= stones[i] <= 1000
解析：直接字面意思去模拟，找出最大值和第二大值，更新值然后递归，直到最后一块或者没有就结束
class Solution {
public int lastStoneWeight(int[] stones) {
int x = 0, y = 0;
int xx = 0, yy = 0;
int n = stones.length;
//先找最大石头 y以及记录y的索引yy
y = stones[0];
yy = 0;
for (int i = 1; i < n; i++) {
if (stones[i] > y) {
y = stones[i];
yy = i;
}
}
// 再找第二大石头 x
// 先初始化x为-1表示没找到
x = -1;
xx = -1;
for (int i = 0; i < n; i++) {
if (i == yy) continue; // 跳过最大石头
if (stones[i] > 0) { // 排除没石头情况
if (stones[i] > x) {
x = stones[i];
xx = i;
}
}
}
// 判断一下如果没找到第二大石头，说明只有一个石头了
if (x == -1) {
return y; // 返回最后一个石头
}
// 更新石头值
if (y > x) {
stones[yy] = y - x;
stones[xx] = 0;
} else {
stones[yy] = 0;
stones[xx] = 0;
}
// 统计剩下的石头数量
int count = 0;
int lastValue = 0;
for (int i = 0; i < n; i++) {
if (stones[i] > 0) {
count++;
lastValue = stones[i];
}
}
// 判断一下数量
if (count == 0) {
return 0;
} else if (count == 1) {
return lastValue;
} else {
// 递归再去处理剩下的石头
return lastStoneWeight(stones);
}
}
}然后想到了更简单的思路，顺序不重要所以用不着模拟，直接在while循环里用Arrays.sort（）排序找最大值第二大值再操作就行
class Solution {
public int lastStoneWeight(int[] stones)
// 简单判断
if (stones.length == 0) return 0;
if (stones.length == 1) return stones[0];
int n = stones.length;
while (stones[n-2]!=0) {//只要第二大值为0，就说明要么只剩一个要么全没了，结束循环直接返回最大值
Arrays.sort(stones);
stones[n-1]=stones[n-1]-stones[n-2];
stones[n-2]=0;
Arrays.sort(stones);
}
return stones[n-1];
}
}再看官解，学到了PriorityQueue优先队列，直接可以poll最小值（最大值），其实思路和上面差不多
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);//括号里为空就是最小优先队列
for (int stone : stones) {
pq.offer(stone);//offer存进去自动就排好了
}
while (pq.size() > 1) {//直到只剩一个值结束
int a = pq.poll();//poll取出最大值
int b = pq.poll();//第二大值
if (a > b) {
pq.offer(a - b);//新值再放进去排列
} //else比如a == b，两个都不做处理，相当于丢掉
}
return pq.isEmpty() ? 0 : pq.poll();
}
}