代码拉取完成，页面将自动刷新
同步操作将从 小牛肉/cs-wiki 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
【题目链接】：
【题目描述】：
实现一个特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
输入描述:
第一行输入一个整数N，表示对栈进行的操作总数。
下面N行每行输入一个字符串S，表示操作的种类。
如果S为"push"，则后面还有一个整数X表示向栈里压入整数X。
如果S为"pop"，则表示弹出栈顶操作。
如果S为"getMin"，则表示询问当前栈中的最小元素是多少。
输出描述:
对于每个getMin操作，输出一行表示当前栈中的最小元素是多少。
示例 1
输入
6
push 3
push 2
push 1
getMin
pop
getMin
输出
1
2
【解题思路】：
使用一个辅助栈，存储当前栈中的最小元素，每次当前栈发生 push 操作时，就将其和辅助栈的栈顶进行比较，如果比栈顶元素还要小，则 push；如果辅助栈的栈顶元素比较小，则将辅助栈的栈顶元素复制一份继续 push 到辅助栈中。
如果当前栈发生 pop 操作，则辅助栈也 pop。
通俗的来说：就是如果当前栈的栈顶元素没有出栈，那这个栈中的最小元素就是辅助栈的栈顶元素。
【具体代码】：
import java.util.*;
public class Main {
public static void main (String[] args) {
MyStack myStack = new MyStack();
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 对栈进行的操作总数
sc.nextLine();
for (int i = 0; i < N; i ++) {
String[] line = sc.nextLine().split(" ");
if (line[0].equals("getMin")) {
System.out.println(myStack.getMin());
}
else if (line[0].equals("push")) {
myStack.push(Integer.valueOf(line[1]));
}
else if (line[0].equals("pop")) {
myStack.pop();
}
}
}
static class MyStack {
private Stack<Integer> stackData; // 存储数据
private Stack<Integer> stackMin; // 存储当前栈中的最小元素
public MyStack() {
this.stackData = new Stack<>();
this.stackMin = new Stack<>();
}
// 压栈
public void push(int newNum) {
stackData.push(newNum);
// 若 stackMin 为空, 则直接将 newNum 压入 stackMin
if (stackMin.isEmpty()) {
stackMin.push(newNum);
}
// 若 newNum > stackMin 栈顶元素, 则将 stackMin 栈顶元素复制一份重复压入 stackMin
else if (newNum > stackMin.peek()) {
stackMin.push(stackMin.peek());
}
// 若 newNum < stackMin 栈顶元素, 则将 newNum 压入 stackMin
else {
stackMin.push(newNum);
}
}
// 出栈
public int pop() {
if (stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
stackMin.pop();
return stackData.pop();
}
// 获取当前栈最小元素
public int getMin() {
if (stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
return stackMin.peek();
}
}
}
【题目链接】：
【题目描述】：
用两个栈实现队列，支持队列的基本操作。
输入描述:
第一行输入一个整数N，表示对队列进行的操作总数。
下面N行每行输入一个字符串S，表示操作的种类。
如果S为"add"，则后面还有一个整数X表示向队列尾部加入整数X。
如果S为"poll"，则表示弹出队列头部操作。
如果S为"peek"，则表示询问当前队列中头部元素是多少。
输出描述:
对于每一个为"peek"的操作，输出一行表示当前队列中头部元素是多少。
示例1
输入
6
add 1
add 2
add 3
peek
poll
peek
输出
1
2
【解题思路】：
【具体代码】：
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
TwoStatckQueue twoStatckQueue = new TwoStatckQueue();
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 对队列进行的操作总数
sc.nextLine();
for (int i = 0; i < N; i ++) {
String[] line = sc.nextLine().split(" ");
if (line[0].equals("peek")) {
System.out.println(twoStatckQueue.peek());
}
else if (line[0].equals("add")) {
twoStatckQueue.add(Integer.valueOf(line[1]));
}
else if (line[0].equals("poll")) {
twoStatckQueue.poll();
}
}
}
// 两个栈实现队列
static class TwoStatckQueue {
private Stack<Integer> stackPush;
private Stack<Integer> stackPop;
public TwoStatckQueue() {
this.stackPush = new Stack<>();
this.stackPop = new Stack<>();
}
// 入队 (从队尾入队)
public void add(int newNum) {
stackPush.push(newNum);
}
// 出队 (队头元素出队)
public int poll() {
if (stackPush.isEmpty() && stackPop.isEmpty()) {
throw new RuntimeException("Queue is empty!");
}
else if (stackPop.isEmpty()) {
while (!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
// 获取队头元素
public int peek() {
if (stackPush.isEmpty() && stackPop.isEmpty()) {
throw new RuntimeException("Queue is empty!");
}
else if (stackPop.isEmpty()) {
while (!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.peek();
}
}
}
【题目链接】：
【题目描述】：
一个栈依次压入1,2,3,4,5，那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后，从栈顶到栈底为1,2,3,4,5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，不能用其他数据结构。
输入描述:
输入数据第一行一个整数N为栈中元素的个数。
接下来一行N个整数X_iXi表示从栈顶依次到栈底的每个元素。
输出描述:
输出一行表示栈中元素逆序后的每个元素
示例1
输入
5
1 2 3 4 5
输出
5 4 3 2 1
【解题思路】：说实话，要不是左神画了图我是真的搞不明白：
【具体代码】：
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<Integer> stack1 = new Stack<>();
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 栈中元素的个数
for (int i = 0; i < N; i ++) {
stack1.push(sc.nextInt());
}
// 这题的输入让人挺无语的：本题的输入是从栈顶到栈底的顺序，而非入栈顺序，因此需要将输入逆序
Stack<Integer> stack2 = new Stack<>();
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
reverse(stack2);
while (!stack2.isEmpty()) {
System.out.print(stack2.pop() + " ");
}
}
// 使用递归逆序一个栈
static void reverse(Stack<Integer> stack) {
// 递归出口
if (stack.isEmpty()) {
return ;
}
// 不断的移除并获取栈底元素
int i = getAndRemoveLastElement(stack);
reverse(stack);
// 将获取到的栈底元素依次重新压栈
stack.push(i);
}
// 使用递归移除栈底元素
static int getAndRemoveLastElement(Stack<Integer> stack) {
// 弹出栈顶元素
int result = stack.pop();
// 递归出口（如果弹出某个元素后栈就空了，那说明这个弹出来的元素就是栈底元素，返回它即可）
if (stack.isEmpty()) {
return result;
}
else {
// 不断地弹出栈顶元素，last 最终就是栈底元素
int last = getAndRemoveLastElement(stack);
// 将弹出来的元素重新入栈
stack.push(result);
// 返回栈底元素
return last;
}
}
}
【题目链接】：
【题目描述】：
给定一个字符串str，判断是不是整体有效的括号字符串(整体有效：即存在一种括号匹配方案，使每个括号字符均能找到对应的反向括号，且字符串中不包含非括号字符)。
输入描述:
输入包含一行，代表（1≤lengthstr≤105）
输出描述:
输出一行，如果str是整体有效的括号字符串，请输出“YES”，否则输出“NO”。
示例 1:
输入
(())
输出
YES
示例 2:
输入
()a()
输出
NO
说明
()a()中包含了 ‘a’，a不是括号字符
【解题思路】：
经典的括号匹配问题，使用一个栈，遇到（ 时就入栈，遇到 ）时就判断栈顶元素是否是（，如果是，则栈顶元素出栈，如果不是，则返回 false。最后判断栈是否为空即可。
【具体代码】：
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
System.out.println(isValidBracket(str) == true ? "YES" : "NO");
}
private static boolean isValidBracket(String str) {
if (str == null || str.length() <= 0) {
return true;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < str.length(); i ++) {
char ch = str.charAt(i);
if (ch == '(') {
stack.push(ch);
}
else if (ch == ')'){
if (stack.isEmpty() || stack.peek() != '(') {
return false;
}
else {
stack.pop();
}
}
else {
return false;
}
}
return stack.isEmpty();
}
}
LeetCode 的20. 有效的括号 — Easy 和这道题目一模一样，只不过多判断几个括号罢了。
【题目描述】：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
示例 1：
输入：s = "()[]{}"
输出：true
示例 2：
输入：s = "([)]"
输出：false
【具体代码】：
class Solution {
public boolean isValid (String s) {
if (s == null || s.length() <= 0) {
return true;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i ++) {
char ch = s.charAt(i);
if (ch == '(' || ch == '[' || ch == '{') {
stack.push(ch);
}
else if (ch == ')') {
if (stack.isEmpty() || stack.peek() != '(') {
return false;
}
stack.pop();
}
else if (ch == ']') {
if (stack.isEmpty() || stack.peek() != '[') {
return false;
}
stack.pop();
}
else if (ch == '}') {
if (stack.isEmpty() || stack.peek() != '{') {
return false;
}
stack.pop();
}
else {
return false;
}
}
return stack.isEmpty();
}
}
【题目链接】：
【题目描述】：
给定一个链表，请判断该链表是否为回文结构。
输入描述:
n 表示链表的长度
ai 表示链表的各个节点的值。
输出描述:
如果为回文结构输出 "true" , 否则输出 "false"。
示例1
输入
4
1 2 2 1
输出
true
【解题思路】：
把整个链表的前半部分压入栈中，压入完成后，再检查栈顶到栈底值出现的顺序是否和链表后半部分的值相对应。注意如果链表长度是奇数，则忽略处于最中间的节点。
【具体代码】：
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 链表长度
// 构造链表
ListNode head = new ListNode(sc.nextInt()); // 第一个节点
ListNode p = head; // 工作指针
for (int i = 1; i < n; i ++) {
p.next = new ListNode(sc.nextInt());
p = p.next;
}
System.out.println(isPalindrome(head));
}
// 判断链表是否回文
private static boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode p = head;
int len = 0; // 链表长度
while (p != null) {
p = p.next;
len ++;
}
// 前一半元素入栈
Stack<ListNode> stack = new Stack<>();
ListNode q = head;
for (int i = 0; i < len/2; i ++) {
stack.push(q);
q = q.next;
}
if (len % 2 != 0) {
// 链表长度是奇数
q = q.next;
}
while (!stack.isEmpty()) {
if (stack.pop().val != q.val) {
return false;
}
q = q.next;
}
return true;
}
// 定义单链表结构
public static class ListNode {
private int val;
private ListNode next;
public ListNode(int val) {
this.val = val;
}
}
}
这里解释一下单调栈：单调栈分为单调递增栈和单调递减栈
单调递增栈操作规则：
单调递减栈操作规则：
【题目链接】：
【题目描述】：
一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？
输入描述:
第一行输入一个N，表示栈中元素的个数
第二行输入N个整数a_iai表示栈顶到栈底的各个元素
输出描述:
输出一行表示排序后的栈中栈顶到栈底的各个元素。
输入
5
5 8 4 3 6
输出
8 6 5 4 3
【解题思路】：将要排序的栈记为 stack，辅助栈成为 help，我们考虑将栈中元素在辅助栈中排好序后再倒入原来的栈中。
题目要求将 statck 中的元素从栈顶到栈底从大到小的顺序排列，那我们的辅助栈从栈底到栈顶就是从大到小的顺序（单调递减栈），最后将辅助栈中的元素依次放进 stack 中即可。
我们在 stack 上执行 pop 操作，将弹出的元素记为 cur：
画个图解释一下：
【具体代码】：
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<Integer> stack1 = new Stack<>();
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 栈中元素的个数
for (int i = 0; i < N; i ++) {
// 栈顶到栈底的各个元素
stack1.push(sc.nextInt());
}
// 本题的输入是从栈顶到栈底的顺序，而非入栈顺序，因此需要将输入逆序
Stack<Integer> stack2 = new Stack<>();
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
sortStackByStack(stack2);
while (!stack2.isEmpty()) {
System.out.print(stack2.pop() + " ");
}
}
private static void sortStackByStack(Stack<Integer> stack) {
Stack<Integer> help = new Stack<>(); // 辅助栈，单调递减栈
while (!stack.isEmpty()) {
int cur = stack.pop();
// 1. 辅助栈为空，直接入辅助栈
if (help.isEmpty()) {
help.push(cur);
}
// 2. 当前元素 <= 辅助栈的栈顶元素，直接入辅助栈
else if (cur <= help.peek()) {
help.push(cur);
}
// 3. 当前元素 > 辅助栈的栈顶元素，将辅助栈的元素依次出栈并重新放入原栈
else {
// 直到当前元素 <= 辅助栈的栈顶元素，就停止辅助栈的出栈操作
while (!help.isEmpty() && cur > help.peek()) {
stack.push(help.pop());
}
// 最后将当前元素加入辅助栈
help.push(cur);
}
}
// 将辅助栈元素导入原栈
while (!help.isEmpty()) {
stack.push(help.pop());
}
}
}
sortStackByStack 方法在代码层面可以稍作精简，当然，上述写法确实是更加通俗易懂：
private static void sortStackByStack(Stack<Integer> stack) {
Stack<Integer> help = new Stack<>(); // 辅助栈，单调递减栈
while (!stack.isEmpty()) {
int cur = stack.pop();
while (!help.isEmpty() && cur > help.peek()) {
stack.push(help.pop());
}
help.push(cur);
}
while (!help.isEmpty()) {
stack.push(help.pop());
}
}
【时间复杂度分析】：
对于单调栈来说，每个元素最多进栈一次，出栈一次，所以遍历的过程中进出栈的操作是时间复杂度为 O(N)，整体的时间复杂度也为 O(N)。
【题目链接】：
【题目描述】：
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
【解题思路】：
首先，最容易想到的，就是暴力解法，对于当前考察的矩形来说，分别向左和向右拓展其边界，直到边界索引对应的矩形高度小于当前考察的矩形的高度，那么以当前考察的矩形作为高的最大矩形面积就是左右边界之间的矩形面积。
public int largestRectangleArea(int[] heights) {
// 定义最终结果初始值为0
int res = 0;
for(int i = 0; i < heights.length; i++) {
// 当前所考察矩形的高度
int curHeight = heights[i];
// 当前考察矩形的左边界索引，初始值为当前索引
int leftIndex = i;
// 如果左边界索引存在且左边界索引对应的矩形高度大于等于当前索引对应的矩形高度
// 表明左侧面积还不能确定，因此左边界索引左移一位
while (leftIndex -1 >= 0 && heights[leftIndex - 1] >= curHeight) {
leftIndex--;
}
// 当前考察矩形的右边界索引，初始值为当前索引值
int rightIndex = i;
// 如果右边界索引存在且右边界索引对应的矩形高度大于等于当前索引对应的矩形高度
// 表明右侧面积还不能确定，因此右边界索引右移一位
while (rightIndex + 1 < heights.length && heights[rightIndex + 1] >= curHeight) {
rightIndex++;
}
// 计算以当前矩形高度为高所能确定的矩形面积，和已记录面积比较，取最大值
res = Math.max(res, (rightIndex - leftIndex +1)*curHeight);
}
return res;
}
当然，时间复杂度是 O(N^2)，这个题目 AC 不了。
考虑使用单调栈用空间换时间，详细可以看这篇大佬的题解，动画 + 文字非常 nice，动画演示 单调栈 84.柱状图中最大的矩形
本题大致思路是这样的，使用单调递增栈：
这里需要注意的是，当栈顶元素出栈后，需要继续看当前考察的新元素值是否大于新的栈顶元素值，如果是，就继续将栈顶元素弹出，然后计算以其值为高的矩形面积，直到当前考察的新元素值大于栈顶元素值时，当前考察元素入栈。
最后，由于最终计算矩形面积时，是用两个柱子的索引来确定矩形宽度的。因此，栈中存储的应该是给定数组的索引。
【具体代码】：
class Solution {
public int largestRectangleArea(int[] heights) {
int res = 0; // 矩形的最大面积
Stack<Integer> stack = new Stack<>(); // 单调递增栈(存储的是下标)
// 添加哨兵
int[] newHeights = new int[heights.length + 2];
newHeights[0] = 0;
newHeights[newHeights.length - 1] = 0;
for (int i = 1; i < newHeights.length-1; i ++) {
newHeights[i] = heights[i - 1];
}
for (int i = 0; i < newHeights.length; i ++) {
// 如果栈不为空并且当前遍历到的矩形高度小于栈顶矩形的高度，
// 则表示以当前栈顶矩形为高的矩形面积可以确定
while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
// 弹出栈顶元素
int cur = stack.pop();
// 获取栈顶元素对应的高
int curHeight = newHeights[cur];
// 计算以被弹出的栈顶矩形作为高所对应的矩形面积
int leftIndex = stack.peek(); // 1. 栈顶元素弹出后，新栈顶元素就是左侧边界
int rightIndex = i; // 2. 右侧边界就是当前正遍历到的矩形下标
int curWidth = rightIndex - leftIndex - 1; // 3. 计算矩形宽度
res = Math.max(res, curWidth * curHeight); // 4. 计算矩形面积
}
// 当前遍历到的矩形索引入栈
stack.push(i);
}
return res;
}
}
【题目链接】：
【题目描述】：
给定一个整型矩阵 map，其中的值只有 0 和 1 两种，求其中全是 1 的所有矩形区域中，最大的矩形区域里 1 的数量。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。
示例 2：
输入：matrix = []
输出：0
示例 3：
输入：matrix = [["1"]]
输出：1
【解题思路】：
这个题目其实上面那题完全一样，只不过这里的柱状图需要我们自己去动手构建。我们来看看如何构建柱状图：
构建出每行的柱状图之后，针对柱状图调用上面那题的解法求最大矩形面积即可。
【具体代码】：
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 矩阵的行数
int m = sc.nextInt(); // 矩阵的列数
// 构造矩阵
int[][] matrix = new int[n][m];
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j ++) {
matrix[i][j] = sc.nextInt();
}
}
// 计算最大矩形面积
int res = maximalRectangle(matrix);
System.out.println(res);
}
static int maximalRectangle(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int maxArea = 0; // 最大矩形面积
int[] height = new int[matrix[0].length]; // 分别以每行作为底，每个位置往上的 1 的数量
for (int i = 0; i < matrix.length; i ++) {
for (int j = 0; j < matrix[0].length; j ++) {
height[j] = matrix[i][j] == 0 ? 0 : height[j] + 1;
}
// 对每一行的柱状图求最大矩形面积
maxArea = Math.max(maxArea, maxRecFromBottom(height));
}
return maxArea;
}
// 计算柱状图中（height数组）最大的矩形
static int maxRecFromBottom(int[] height) {
int res = 0; // 最大矩形面积
Stack<Integer> stack = new Stack<>(); // 单调递增栈
// 添加哨兵
int[] newHeights = new int[height.length + 2];
newHeights[0] = 0;
newHeights[newHeights.length - 1] = 0;
for (int i = 1; i < newHeights.length-1; i ++) {
newHeights[i] = height[i - 1];
}
for (int i = 0; i < newHeights.length; i ++) {
// 如果栈不为空并且当前遍历到的矩形高度小于栈顶矩形的高度，
// 则表示以当前栈顶矩形为高的矩形面积可以确定
while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
// 弹出栈顶元素
int cur = stack.pop();
// 获取栈顶元素对应的高
int curHeight = newHeights[cur];
// 计算以被弹出的栈顶矩形作为高所对应的矩形面积
int leftIndex = stack.peek(); // 1. 栈顶元素弹出后，新栈顶元素就是左侧边界
int rightIndex = i; // 2. 右侧边界就是当前正遍历到的矩形下标
int curWidth = rightIndex - leftIndex - 1; // 3. 计算矩形宽度
res = Math.max(res, curWidth * curHeight); // 4. 计算矩形面积
}
// 当前遍历到的矩形索引入栈
stack.push(i);
}
return res;
}
}
【题目链接】：
【题目描述】：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
【解题思路】：
使用单调递减栈，和 LC84 的思路基本一模一样，甚至都不需要使用哨兵技巧。
【具体代码】：
class Solution {
public int trap(int[] height) {
Stack<Integer> stack = new Stack<>(); // 单调递减栈(存储的是下标)
int n = height.length;
int sum = 0; // 总共储水量
for (int i = 0; i < n; i ++) {
// 栈不为空并且当前遍历到的柱子高度大于栈顶柱子的高度，
// 则表示以当前栈顶柱子作为底所对应的储水量可以确定
while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
// 弹出栈顶元素(水坑的底部)
int cur = stack.pop();
// 计算以被弹出的栈顶柱子作为底所对应的储水量
if (stack.isEmpty()) {
// 接下来我们需要获取新栈顶的元素，所以此处需要加个判断，保证新栈顶元素存在，否则会报错
break;
}
int leftIndex = stack.peek(); // 栈顶元素弹出后，新栈顶元素就是左侧边界
int rightIndex = i; // 右侧边界就是当前正遍历到的柱子下标
int distance = rightIndex - leftIndex - 1; // 水坑的宽度
int h = Math.min(height[rightIndex], height[leftIndex]) - height[cur]; // 水坑的高度
sum += distance * h;
}
// 当前遍历到的柱子索引入栈
stack.push(i);
}
return sum;
}
}
【题目链接】：
【题目描述】：
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
【解题思路】：
使用单调递减栈，这样，当我们加入一个元素 i 的时候，就知道当前栈顶元素在数组中右面第一个比栈顶元素大的元素就是 i。
【具体代码】：
class Solution {
public int[] dailyTemperatures(int[] T) {
Stack<Integer> stack = new Stack<>(); // 单调递减栈
int n = T.length;
int[] res = new int[n];
for (int i = 0; i < n; i ++) {
int index = 0;
while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
res[stack.peek()] = i - stack.peek();
stack.pop();
}
stack.push(i);
}
return res;
}
}
【题目链接】：
【题目描述】：
给定一个不含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。
输入描述:
第一行输入一个数字 n，表示数组 arr 的长度。
以下一行输出 n个数字，表示数组的值。
输出描述:
输出n行，每行两个数字 L 和 R，如果不存在，则值为-1，下标从0开始。
示例1
输入
7
3 4 1 5 6 2 7
输出
-1 2
0 2
-1 -1
2 5
3 5
2 -1
5 -1
【解题思路】：
做了这么多单调栈的题目，各位大概也找到规律了吧，如果题目找的是某个比较小的值，就使用单调递增栈，如果找的是某个比较大的值，就是用单调递减栈。
本题使用单调递增栈，如果栈顶 x 位置被弹出，那么在栈中位于 x 位置下面的位置就是 x 位置左边离 x 位置最近且值比 arr[x]小的位置（这个很好理解）；当前遍历到的位置就是 x 位置右边离 x 位置最近且值比 arr[x]小的位置，解释一下这个：
举个例子：
不过，这个题目和我们上面的题目有所不同的是，在循环一遍完之后，我们需要对栈中剩下的元素继续做处理。栈中剩下的元素就是那些在数组的右边不存在比他们小的数的元素。接着上面的例子，遍历阶段结束后，清算栈中剩下的位置。
【具体代码】：
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i ++) {
arr[i] = sc.nextInt();
}
int[][] res = getNearLessNoRepeat(arr);
for (int i = 0; i < n; i++) {
System.out.println(res[i][0] + " " + res[i][1]);
}
}
private static int[][] getNearLessNoRepeat(int[] arr) {
int n = arr.length;
Stack<Integer> stack = new Stack<>(); // 单调递增栈
int[][] res = new int[n][2];
for (int i = 0; i < n; i ++) {
res[i][0] = -1;
res[i][1] = -1;
}
for (int i = 0; i < n; i ++) {
while (!stack.isEmpty() && arr[i] <= arr[stack.peek()]) {
int cur = stack.pop();
int leftIndex = stack.isEmpty() ? -1 : stack.peek();
int rightIndex = i;
res[cur][0] = leftIndex;
res[cur][1] = rightIndex;
}
stack.push(i);
}
// 清算栈中剩下的位置
while (!stack.isEmpty()) {
int cur = stack.pop();
int leftIndex = stack.isEmpty() ? -1: stack.peek();
int rightIndex = -1;
res[cur][0] = leftIndex;
res[cur][1] = rightIndex;
}
return res;
}
}
【题目链接】：
【题目描述】：
给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。
输入描述:
第一行输入一个数字 n，表示数组 arr 的长度。
以下一行输入 n 个数字，表示数组的值
输出描述:
输出n行，每行两个数字 L 和 R，如果不存在，则值为 -1，下标从 0 开始。
【解题思路】：
这个题目和上个题目解题思路基本一致，整体的框架都是一样的。不过由于重复值的存在，我们的栈需要存储的就不是一个一个的数了，而是一个一个的 List，把值相同的元素放在同一个 List 里面。
【具体代码】：
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i ++) {
arr[i] = sc.nextInt();
}
int[][] res = getNearLess(arr);
for (int i = 0; i < n; i++) {
System.out.println(res[i][0] + " " + res[i][1]);
}
}
private static int[][] getNearLess (int[] arr) {
int n = arr.length;
Stack<List<Integer>> stack = new Stack<>(); // 单调递增栈
int[][] res = new int[n][2];
for (int i = 0; i < n; i ++) {
res[i][0] = -1;
res[i][1] = -1;
}
for (int i = 0; i < n; i ++) {
while (!stack.isEmpty() && arr[i] < arr[stack.peek().get(0)]) {
List<Integer> curs = stack.pop();
int leftIndex = stack.isEmpty() ? -1 :
stack.peek().get(stack.peek().size()-1); // 取决于列表中最晚加入的那个
int rightIndex = i;
for (int cur : curs) { // 对于这些重复元素来说，它们的结果是相同的
res[cur][0] = leftIndex;
res[cur][1] = rightIndex;
}
}
// stack.push(i); 需要判断一下单独封装成 List 还是直接加入
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
stack.peek().add(i);
}
else {
List<Integer> list = new ArrayList<>();
list.add(i);
stack.push(list);
}
}
// 清算栈中剩下的位置
while (!stack.isEmpty()) {
List<Integer> curs = stack.pop();
int leftIndex = stack.isEmpty() ? -1 :
stack.peek().get(stack.peek().size()-1); // 取决于列表中最晚加入的那个
int rightIndex = -1;
for (int cur : curs) {
res[cur][0] = leftIndex;
res[cur][1] = rightIndex;
}
}
return res;
}
}
只能通过 75%，考虑是否数据量太大后 IO 交互太频繁，稍作修改一下，使用 StringBuilder 存储结果，然后做一次输出结果，100% 通过，nice！
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i ++) {
arr[i] = sc.nextInt();
}
int[][] res = getNearLess(arr);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(res[i][0]);
sb.append(" ");
sb.append(res[i][1]);
sb.append("\n");
}
System.out.print(sb);
}
【题目链接】：
【题目描述】：
一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。比如，{3,1,2,4,5}，{4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。3->1->2->4->5->3 方向叫作 next 方向(逆时针)，3->5->4->2->1->3 方向叫作 last 方向(顺时针)。
山峰 A 和 山峰 B 能够相互看见的条件为:
如果 A 和 B 是同一座山，认为不能相互看见。
如果 A 和 B 是不同的山，并且在环中相邻，认为可以相互看见。
如果 A 和 B 是不同的山，并且在环中不相邻，假设两座山高度的最小值为 min。如果 A 通过 next 方向到 B 的途中没有高度比 min 大的山峰，或者 A 通过 last 方向到 B 的途中没有高度比 min 大的山峰，认为 A 和 B 可以相互看见。
问题如下：
给定一个含有负数可能有重复值的数组 arr，请问有多少对山峰能够相互看见？
输入描述:
第一行给出一个整数 n，表示山峰的数量。
以下一行 n 个整数表示各个山峰的高度。
输出描述:
输出一行表示答案。
示例1
输入
5
3 1 2 4 5
输出
7
【解题思路】：
说实话这个题目理解题意比较重要。首先需要明白的是，我们要找的是山峰对，也就是每两个山脉。
我们只用高度小的山峰去找高度大的山峰，而永远不用高度大的山峰去找高度小的山峰。
比如题目描述中的例子，从 2 出发按照“小找大”原则，会找到(2,3)和(2,4)，但是不去尝试 2能不能看到 1，因为这是“大找小”，而不是“小找大”。(1,2)这一对可见山峰不会错过，因为从 1 出发按照“小找大”原则找的时候会找到这一对。从每一个位置出发，都按照“小找大”原则找到山峰对的数量，就是总的可见山峰对数量。
根据小找大原则，我们要找的是某个比较大的值，所以使用的是单调递减栈。
首先遍历一次环形山结构，找到最大值的位置，将其入栈。如果最大值不止一个，找哪一个最大值都行。比如图 1-10 中 5 是最大值且不止一个，找到哪个都行，我们选择最下方的 5。准备一个栈，记为 stack<Record>，stack 中放入的是如下数据结构：
private static class Record {
private int value; // 山的高度
private int times; // 这个高度出现的次数
public Record(int value) {
this.value = value;
this.times = 1;
}
}
接下来从最大值开始沿着 next 方向准备再遍历一遍环形山。stack 中先放入(5,1)，表示 5 这个高度，收集 1 个。以后放入记录时，都保证第一维的数字从顶到底是依次增大的。目前 stack 从顶到底为：(5,1)。
和单调栈那题一样，接下来我们进入清算阶段：
【具体代码】：
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i ++) {
arr[i] = sc.nextInt();
}
System.out.println(getVisibleNum(arr));
}
private static int getVisibleNum(int[] arr) {
int res = 0;
int n = arr.length;
// 找到环中最大高度的山峰
int maxIndex = 0; // 最大高度山峰的下标
for (int i = 1; i < n; i ++) {
maxIndex = arr[i] > arr[maxIndex] ? i : maxIndex;
}
Stack<Record> stack = new Stack<>(); // 单调递减栈
// 先把(最大高度,1)这个记录入栈
stack.push(new Record(arr[maxIndex]));
// 从最大值位置的下一个位置开始沿 next 方向遍历
int index = nextIndex(maxIndex, n);
// 用 “小找大” 的方式统计所有可见山峰对
while (index != maxIndex) {
while (arr[index] > stack.peek().value) { // 此处不必进行栈的判空，因为最大值已经入栈，不会被弹出
int k = stack.pop().times;
if (k == 1) {
res += 2;
}
else if (k > 1) {
res += getInternalSum(k) + 2*k;
}
}
// stack.push(new Record(arr[index]);
if (stack.peek().value == arr[index]) {
stack.peek().times ++;
}
else {
stack.push(new Record(arr[index]));
}
// index ++;
index = nextIndex(index, n);
}
// 清算阶段
// 第 1 阶段 (栈中存留的元素个数大于 2)
while (stack.size() > 2) {
int times = stack.pop().times;
res += getInternalSum(times) + 2 * times;
}
// 第 2 阶段 (栈中还剩两个元素)
if (stack.size() == 2) {
int times = stack.pop().times;
res += getInternalSum(times) + (
(stack.peek().times == 1) ? times : times * 2);
}
// 第 3 阶段 (栈中还剩一个元素)
if (stack.size() == 1) {
int times = stack.pop().times;
res += ((times == 1) ? 0 : getInternalSum(times));
}
return res;
}
private static class Record {
private int value; // 山的高度
private int times; // 这个高度出现的次数
public Record(int value) {
this.value = value;
this.times = 1;
}
}
// 获取环形山脉中当前位置的的下一个位置
private static int nextIndex(int cur, int n) {
return (cur < n-1) ? (cur + 1) : 0;
}
// 计算 C(2,k)
private static int getInternalSum(int k) {
return k == 1 ? 0 : (k * ( k - 1) / 2);
}
}
【题目链接】：
【题目描述】：
有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置，求每一种窗口状态下的最大值。（如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值）
输入描述:
第一行输入n和w，分别代表数组长度和窗口大小
第二行输入n个整数X_iXi，表示数组中的各个元素
输出描述:
输出一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值
示例1
输入
8 3
4 3 5 4 3 3 6 7
输出
5 5 5 4 6 7
说明
例如，数组为[4，3，5，4，3，3，6，7]，窗口大小为3时：
[4 3 5] 4 3 3 6 7 窗口中最大值为5
4 [3 5 4] 3 3 6 7 窗口中最大值为5
4 3 [5 4 3] 3 6 7 窗口中最大值为5
4 3 5 [4 3 3] 6 7 窗口中最大值为4
4 3 5 4 [3 3 6] 7 窗口中最大值为6
4 3 5 4 3 [3 6 7] 窗口中最大值为7
输出的结果为{5 5 5 4 6 7}
【解题思路】：最粗暴的思路当然就是循环遍历，使用两个指针，然后获取这两个指针之间的最大数，两个指针不断 +1，但是这个时间复杂度是 O(N x M)，我们可以使用双端队列 LinkedList 来把时间复杂度降到 O(N)，这里使用的单调递增队列（从队尾到队头单调递增），这样我们的队头元素就是当前窗口的最大元素。
单调递增的双端队列的操作规则：
双端队列中存放数组的下标，我们把这个队列命名为 qmax，根据题意，qmax 需要维护一个大小为 w 的窗口，其队头元素就是当前窗口中最大元素的下标：
下面举个例子：
画个图帮助理解下：
【具体实现】：
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 数组长度
int w = sc.nextInt(); // 窗口大小
int[] nums = new int[n];
for (int i = 0; i < n; i ++) {
nums[i] = sc.nextInt();
}
int[] res = getMaxWindow(nums, w);
for (int num : res) {
System.out.print(num + " ");
}
}
// 获取 nums 数组中每个大小为 w 的窗口中的最大值
static int[] getMaxWindow(int[] nums, int w) {
int n = nums.length;
LinkedList<Integer> qmax = new LinkedList<>(); // 单调递增的双端队列
int[] res = new int[n - w + 1];
int index = 0;
for (int i = 0; i < n; i ++) {
// 1. 队列为空，直接入队
if (qmax.isEmpty()) {
qmax.addLast(i);
}
// 2. 当前元素 < 队尾元素，直接入队
else if (nums[i] < nums[qmax.peekLast()]) {
qmax.addLast(i);
}
// 3. 当前元素 >= 队尾元素，则将队尾元素依次出队
else {
// 直到队尾元素 <= 当前元素，就停止出队操作
while (!qmax.isEmpty() && nums[i] >= nums[qmax.peekLast()]) {
qmax.pollLast();
}
// 最后将当前元素从队尾入队
qmax.addLast(i);
}
// 栈顶元素过期，弹出（维护一个大小为 w 的窗口）
if (qmax.peekFirst() == i-w) {
qmax.pollFirst();
}
// 队头就是当前窗口的最大元素
if (i >= w-1) {
res[index ++] = nums[qmax.peekFirst()];
}
}
return res;
}
}
getMaxWindow 方法在代码层面可以稍作精简，当然，上述写法确实是更加通俗易懂：
static int[] getMaxWindow(int[] nums, int w) {
int n = nums.length;
LinkedList<Integer> qmax = new LinkedList<>();
int[] res = new int[n - w + 1]; // 存储每个窗口中的最大值
int index = 0; // res 下标
for (int i = 0; i < n; i ++) {
while (!qmax.isEmpty() && nums[i] >= nums[qmax.peekLast()]) {
qmax.pollLast();
}
qmax.addLast(i);
if (qmax.peekFirst() == i-w) {
qmax.pollFirst();
}
if (i >= w - 1) {
res[index ++] = nums[qmax.peekFirst()];
}
}
return res;
}
【题目链接】：
【题目描述】：
给定数组 arr 和整数 num，共返回有多少个子数组满足如下情况：
max(arr[i...j])表示子数组arr[i...j]中的最大值，min[arr[i...j])表示子数组arr[i...j]中的最小值。
输入描述:
第一行输入两个数 n 和 num，其中 n 表示数组 arr 的长度
第二行输入n个整数X_iXi，表示数组arr中的每个元素
输出描述:
输出给定数组中满足条件的子数组个数
示例1
输入
5 2
1 2 3 4 5
输出
12
【解题思路】：
首先从题目中我们可以得出两个结论：
我们可以维护两个双端队列，一个单调递增 qmax，一个单调递减 qmin，如果 qmax 的队头元素减去 qmin 的队头元素 <= 指定值 num，那么队列中维护的这个子数组就是满足题目条件的。
【具体代码】：
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 数组 arr 的长度
int num = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i ++) {
arr[i] = sc.nextInt();
}
int res = getNum(arr, num);
System.out.println(res);
}
private static int getNum(int[] arr, int num) {
int n = arr.length;
int res = 0;
LinkedList<Integer> qmin = new LinkedList<>(); // 单调递减的双端队列
LinkedList<Integer> qmax = new LinkedList<>(); // 单调递增的双端队列
int i = 0;
int j = 0;
while (i < n) {
while (j < n) {
// 维护单调递减的双端队列
while (!qmin.isEmpty() && arr[j] <= arr[qmin.peekLast()]) {
qmin.pollLast();
}
qmin.addLast(j);
// 维护单调递增的双端队列
while (!qmax.isEmpty() && arr[j] >= arr[qmax.peekLast()]) {
qmax.pollLast();
}
qmax.addLast(j);
// 若不满足题目条件，则停止 j 继续向右扩
if (arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num) {
break;
}
j ++;
}
// 记录满足条件的子数组数量
res += j - i;
// i 接下来将会向右扩，如果当前 qmin 或 qmax 的队头就是 i，则将其弹出
if (qmax.peekFirst() == i) {
qmax.pollFirst();
}
if (qmin.peekFirst() == i) {
qmin.pollFirst();
}
i ++;
}
return res;
}
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。