跳至主要內容

2.3 栈

2.3 栈

栈的定义

定义

栈（Stack） 是一种“操作受限”的线性表，只允许在一端插入和删除数据。后进者先出，先进者后出，这就是典型的“栈”结构。

栈是一种 后进先出（Last In First Out） 的线性表，简称为 LIFO 结构。

有一个非常贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。

我们把栈中允许插入和删除的一端称为 栈顶（top）；另一端则称为 栈底（bottom）。当表中没有任何数据元素时，称之为 空栈。

栈主要包含两个操作，入栈和出栈，入栈push()就是在栈顶插入一个数据；出栈pop()就是从栈顶删除一个数据。

我们可以从两个方面来解释一下栈的定义：

  • 「线性表」

    栈首先是一个线性表，栈中元素具有前驱后继的线性关系。栈中元素按照 a1,a2,...,an 的次序依次进栈。栈顶元素为 an。

  • 「后进先出原则」

    元素进入栈或者退出退栈是按照 后进先出（Last In First Out） 的原则进行的。每次删除的总是栈中当前的栈顶元素，即最后进入栈的元素。而在进栈时，最先进入栈的元素一定在栈底，最后进入栈的元素一定在栈顶。

栈的实现

栈既可以用数组来实现，也可以用链表来实现。

用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

顺序栈

// 基于数组实现的顺序栈
class ArrayStack {
	constructor() {
		this._stack = []; // 栈中的数据
	}

	// 入栈
	push(data) {
		this._stack.push(data);
	}
	// 出栈
	pop() {
		return this._stack.pop();
	}
	// 清空栈
	clear() {
		this._stack = [];
	}
	// 获取栈中元素的数量
	count() {
		return this._stack.length;
	}
	// 打印栈
	print() {
		console.log(this._stack);
	}
}
👉 查看代码测试 👈
const stack = new ArrayStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.print(); // output: [1, 2, 3]
stack.pop();
stack.print(); // output: [1, 2]
console.log(stack.count()); // output: 2

链式栈

// 定义节点类
class Node {
	constructor(data) {
		this.data = data; // 节点中的数据
		this.next = null; // 下一个节点
	}
}

// 基于链表实现的链式栈
class LinkedListStack {
	constructor() {
		this.head = null; // 栈顶元素
		this.length = 0; // 栈中元素的个数
	}
	// 入栈
	push(data) {
		let newNode = new Node(data);
		newNode.next = this.head;
		this.head = newNode;
		this.length++;
	}

	// 出栈
	pop() {
		let data = this.head.data;
		this.head = this.head.next;
		this.length--;
		return data;
	}
	// 清空栈
	clear() {
		this.head.next = null;
		this.head = null;
	}
	// 获取栈中元素的数量
	count() {
		return this.length;
	}
	// 打印栈
	print() {
		console.log(this.head);
	}
}
👉 查看代码测试 👈
const stack = new LinkedListStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.print();
// output: Node {data: 3, next: Node {data: 2, next: Node {data: 1, next: null}}}

stack.pop();
stack.print();
// output: Node {data: 2, next: Node {data: 1, next: null}}

console.log(stack.count()); // output: 2

空间复杂度：

不管是顺序栈还是链式栈，我们存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

时间复杂度：

不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。

栈的应用

从功能上来说，数组或链表可以完全替代栈，但特定的数据结构是对特定场景的抽象，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。

1. 表达式求值

一个常见的应用场景是，编译器利用栈来实现表达式求值。

相关题目

📌 227. 基本计算器 II - LeetCodeopen in new window

💻 题目大意

给定一个字符串表达式 s，表达式中所有整数为非负整数，运算符只有 +、-、*、/，没有括号。实现一个基本计算器来计算并返回它的值。

示例：

输入：s = "3+2*2"

输出：7

输入：s = " 3/2 "

输出：1

说明：

  • 1 ≤ s.length ≤ 3∗10^5
  • s 由整数和算符（+、-、*、/）组成，中间由一些空格隔开
  • s 表示一个有效表达式
  • 表达式中的所有整数都是非负整数，且在范围 [0, 2^31 − 1]内
  • 题目数据保证答案是一个 32-bit 整数

💡 解题思路

通过两个栈来实现。其中一个是保存操作数的栈，另一个是保存运算符的栈。从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。

如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

比如：3 + 5 * 8 - 6：

💎 代码

👉 查看代码 👈
// TODO: add code

#### 📌 [227. 基本计算器 II - LeetCode](https://2xiao.github.io/leetcode-js/problem/0227.html)

#### 💻 **题目大意**

给定一个字符串表达式 s，表达式中所有整数为非负整数，运算符只有 +、-、\*、/，没有括号。实现一个基本计算器来计算并返回它的值。

**示例**：

> 输入：s = "3+2\*2"
>
> 输出：7

> 输入：s = " 3/2 "
>
> 输出：1

**说明**：

- `1 ≤ s.length ≤ 3∗10^5`
- `s` 由整数和算符（`+、-、*、/`）组成，中间由一些空格隔开
- `s` 表示一个有效表达式
- 表达式中的所有整数都是非负整数，且在范围` [0, 2^31 − 1]`内
- 题目数据保证答案是一个 `32-bit` 整数

#### 💡 **解题思路**

通过两个栈来实现。其中一个是保存操作数的栈，另一个是保存运算符的栈。从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。

如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

比如：`3 + 5 * 8 - 6`：

![](../image/2-3-2.png)

#### 💎 **代码**

<details>
<summary>👉 查看代码 👈</summary>

```javascript
// TODO: add code
```

</details>

2. 括号匹配

还可以借助栈来检查表达式中的括号是否匹配。

相关题目

📌 20. 有效的括号 - LeetCodeopen in new window

💻 题目大意

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串 s 是否有效（即括号是否匹配）。

示例：

输入：s = "()"

输出：True

输入：s = "()[]{}"

输出：True

说明：

有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。

💡 解题思路

用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；

当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。

如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。

当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。

💎 代码

👉 查看代码 👈
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
	const len = s.length;
	if (len === 0) return true;

	let stack = [];
	for (let i = 0; i < len; i++) {
		let v = s[i];
		if (v === '{' || v === '(' || v === '[') {
			stack.push(v);
		} else if (
			(v === '}') & (stack.length > 0) & (stack[stack.length - 1] === '{') ||
			(v === ')') & (stack.length > 0) & (stack[stack.length - 1] === '(') ||
			(v === ']') & (stack.length > 0) & (stack[stack.length - 1] === '[')
		) {
			stack.pop();
		} else {
			return false;
		}
	}
	return stack.length === 0;
};

#### 📌 [20. 有效的括号 - LeetCode](https://2xiao.github.io/leetcode-js/problem/0020.html)

#### 💻 **题目大意**

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串 s 是否有效（即括号是否匹配）。

**示例**：

> 输入：s = "()"
>
> 输出：True

> 输入：s = "()[]{}"
>
> 输出：True

**说明**：

有效字符串需满足：

- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。

#### 💡 **解题思路**

用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；

当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“`(`”跟“`)`”匹配，“`[`”跟“`]`”匹配，“`{`”跟“`}`”匹配，则继续扫描剩下的字符串。

如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。

当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。

#### 💎 **代码**

<details>
<summary>👉 查看代码 👈</summary>

```javascript
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
	const len = s.length;
	if (len === 0) return true;

	let stack = [];
	for (let i = 0; i < len; i++) {
		let v = s[i];
		if (v === '{' || v === '(' || v === '[') {
			stack.push(v);
		} else if (
			(v === '}') & (stack.length > 0) & (stack[stack.length - 1] === '{') ||
			(v === ')') & (stack.length > 0) & (stack[stack.length - 1] === '(') ||
			(v === ']') & (stack.length > 0) & (stack[stack.length - 1] === '[')
		) {
			stack.pop();
		} else {
			return false;
		}
	}
	return stack.length === 0;
};
```

</details>

3. 浏览器历史记录

另一个常见的应用场景是浏览器的前进后退功能。

相关题目

📌 1472. 设计浏览器历史记录 - LeetCodeopen in new window

💻 题目大意

设计一个只支持单个标签页的 浏览器 ，最开始浏览的网页是 homepage ，可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。

请你实现 BrowserHistory 类：

  • BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
  • void visit(string url) 从当前页跳转访问 url 对应的页面。执行此操作会把浏览历史前进的记录全部删除。
  • string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。请返回后退 至多 steps 步以后的 url 。
  • string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。请返回前进 至多 steps 步以后的 url 。

示例：

BrowserHistory browserHistory = new BrowserHistory("leetcode.com");

browserHistory.visit("google.com"); // 访问 "google.com"

browserHistory.visit("facebook.com"); // 访问 "facebook.com"

browserHistory.visit("youtube.com"); // 访问 "youtube.com"

browserHistory.back(1); // 后退到 "facebook.com"

browserHistory.back(1); // 后退到 "google.com"

browserHistory.forward(1); // 前进到 "facebook.com"

browserHistory.visit("linkedin.com"); // 访问 "linkedin.com"

browserHistory.forward(2); // 无法前进任何步数。

browserHistory.back(2); // 后退两步依次先到 "facebook.com" ，然后到 "google.com"

browserHistory.back(7); // 只能后退一步到 "leetcode.com"

说明：

  • 1 <= homepage.length <= 20
  • 1 <= url.length <= 20
  • 1 <= steps <= 100
  • homepage 和 url 都只包含 '.' 或者小写英文字母。
  • 最多调用 5000 次 visit， back 和 forward 函数。

💡 解题思路

使用栈来存储浏览器的访问历史，使用 cur_index 变量来存储当前访问的网址在栈中的位置。

  • visit：
    • 先清空 cur_index 之后的历史记录；
    • 将 url 放入栈顶；
    • 将 cur_index 指向栈顶；
  • back：比较栈中存储的历史记录数 n 和 steps 的大小，最多只能倒退 n 步；
  • forward: 比较 cur_index 之后的历史记录数 m 和 steps 的大小，最多只能前进 m 步；

💎 代码

👉 查看代码 👈
class BrowserHistory {
	// @param {string} homepage
	constructor(homepage) {
		this.history = [homepage];
		this.cur_index = 0;
	}

	// @param {string} url
	// @return {void}
	visit(url) {
		// clear forward history
		this.history = this.history.slice(0, this.cur_index + 1);
		this.history.push(url);
		this.cur_index++;
	}

	// @param {number} steps
	// @return {string}
	back(steps) {
		this.cur_index = Math.max(0, this.cur_index - steps);
		return this.history[this.cur_index];
	}

	// @param {number} steps
	// @return {string}
	forward(steps) {
		this.cur_index = Math.min(this.history.length - 1, this.cur_index + steps);
		return this.history[this.cur_index];
	}
}

#### 📌 [1472. 设计浏览器历史记录 - LeetCode](https://2xiao.github.io/leetcode-js/problem/1472.html)

#### 💻 **题目大意**

设计一个只支持单个标签页的 **浏览器** ，最开始浏览的网页是 `homepage` ，可以访问其他的网站 `url` ，也可以在浏览历史中后退 `steps` 步或前进 `steps` 步。

请你实现 `BrowserHistory` 类：

- `BrowserHistory(string homepage)` ，用 `homepage` 初始化浏览器类。
- `void visit(string url)` 从当前页跳转访问 `url` 对应的页面。执行此操作会把浏览历史前进的记录全部删除。
- `string back(int steps)` 在浏览历史中后退 `steps` 步。如果你只能在浏览历史中后退至多 `x` 步且 `steps > x` ，那么你只后退 `x` 步。请返回后退 至多 `steps` 步以后的 `url` 。
- `string forward(int steps)` 在浏览历史中前进 `steps` 步。如果你只能在浏览历史中前进至多 x 步且 `steps > x` ，那么你只前进 `x` 步。请返回前进 至多 `steps` 步以后的 `url` 。

**示例**：

> BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
>
> browserHistory.visit("google.com"); // 访问 "google.com"
>
> browserHistory.visit("facebook.com"); // 访问 "facebook.com"
>
> browserHistory.visit("youtube.com"); // 访问 "youtube.com"
>
> browserHistory.back(1); // 后退到 "facebook.com"
>
> browserHistory.back(1); // 后退到 "google.com"
>
> browserHistory.forward(1); // 前进到 "facebook.com"
>
> browserHistory.visit("linkedin.com"); // 访问 "linkedin.com"
>
> browserHistory.forward(2); // 无法前进任何步数。
>
> browserHistory.back(2); // 后退两步依次先到 "facebook.com" ，然后到 "google.com"
>
> browserHistory.back(7); // 只能后退一步到 "leetcode.com"

**说明**：

- `1 <= homepage.length <= 20`
- `1 <= url.length <= 20`
- `1 <= steps <= 100`
- `homepage` 和 `url` 都只包含 `'.'` 或者小写英文字母。
- 最多调用 `5000` 次 `visit，` `back` 和 `forward` 函数。

#### 💡 **解题思路**

使用栈来存储浏览器的访问历史，使用 `cur_index` 变量来存储当前访问的网址在栈中的位置。

- `visit`：
  - 先清空 `cur_index` 之后的历史记录；
  - 将 `url` 放入栈顶；
  - 将 `cur_index` 指向栈顶；
- `back`：比较栈中存储的历史记录数 `n` 和 `steps` 的大小，最多只能倒退 `n` 步；
- `forward`: 比较 `cur_index` 之后的历史记录数 `m` 和 `steps` 的大小，最多只能前进 `m` 步；

#### 💎 **代码**

<details>
<summary>👉 查看代码 👈</summary>

```javascript
class BrowserHistory {
	// @param {string} homepage
	constructor(homepage) {
		this.history = [homepage];
		this.cur_index = 0;
	}

	// @param {string} url
	// @return {void}
	visit(url) {
		// clear forward history
		this.history = this.history.slice(0, this.cur_index + 1);
		this.history.push(url);
		this.cur_index++;
	}

	// @param {number} steps
	// @return {string}
	back(steps) {
		this.cur_index = Math.max(0, this.cur_index - steps);
		return this.history[this.cur_index];
	}

	// @param {number} steps
	// @return {string}
	forward(steps) {
		this.cur_index = Math.min(this.history.length - 1, this.cur_index + steps);
		return this.history[this.cur_index];
	}
}
```

</details>

4. 函数调用栈

还有一个比较经典的应用场景就是函数调用栈。

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。更好地理解，来看下这段代码的执行过程。

function main() {
    let a = 1;
    let ret = 0;
    let res = 0;
    ret = add(3, 5);
    res = a + ret;
    console.log("%d", res);
    reuturn 0;
}

function add(x, y) {
    let sum = 0;
    sum = x + y;
    return sum;
}

从代码中可以看出，main()函数调用了 add()函数，获取计算结果，并且与临时变量 a 相加，最后打印 res 的值。在执行到 add()函数时，函数调用栈的情况如下所示：

单调栈

定义

单调栈（Monotone Stack） ：一种特殊的栈。在栈的先进后出规则基础上，要求从栈顶到栈底的元素是单调递增或者单调递减。

单调递增栈

单调递增栈：只有比栈顶元素小的元素才能直接进栈，否则需要先将栈中比当前元素小的元素出栈，再将当前元素入栈。

单调递增栈的入栈、出栈过程如下：

  • 假设当前进栈元素为 x，如果 x 比栈顶元素小，则直接入栈；
  • 否则从栈顶开始遍历栈中元素，把小于 x 或者等于 x 的元素弹出栈，直到遇到一个大于 x 的元素为止，然后再把 x 压入栈中；

比如，将数组 [2, 7, 5, 4, 6] 依次入栈，则过程是：

操作结果
2 入栈[2]
2 出栈， 7 入栈[7]
5 入栈[7, 5]
4 入栈[7, 5, 4]
4 出栈， 5 出栈， 6 入栈[7, 6]

最终栈中元素为 [7, 6]。

单调递减栈

单调递减栈：只有比栈顶元素大的元素才能直接进栈，否则需要先将栈中比当前元素大的元素出栈，再将当前元素入栈。

单调递减栈的入栈、出栈过程如下：

  • 假设当前进栈元素为 x，如果 x 比栈顶元素大，则直接入栈。
  • 否则从栈顶开始遍历栈中元素，把大于 x 或者等于 x 的元素弹出栈，直到遇到一个小于 x 的元素为止，然后再把 x 压入栈中。

比如，将数组 [2, 7, 5, 4, 6] 依次入栈，则过程是：

操作结果
2 入栈[2]
7 入栈[2, 7]
7 出栈，5 入栈[2, 5]
5 出栈，4 入栈[2, 4]
6 入栈[2, 4, 6]

最终栈中元素为 [2, 4, 6]。

单调栈的应用

1. 下一个更大元素

相关题目

📌 496. 下一个更大元素 I - LeetCodeopen in new window

💻 题目大意

给定两个没有重复元素的数组 nums1 和 nums2 ，其中 nums1 是 nums2 的子集。找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指： x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1。

请设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案。

示例：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2]

输出：[-1,3,-1]

输入：nums1 = [2,4], nums2 = [1,2,3,4]

输出：[3,-1]

说明：

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 10^4
  • nums1 和 nums2 中所有整数互不相同
  • nums1 中的所有整数同样出现在 nums2 中

💡 解题思路

  • 使用单调递增栈；
  • 因为 nums1 是 nums2 的子集，所以我们可以先遍历一遍 nums2，并构造单调递增栈；
  • 求出 nums2 中每个元素右侧下一个更大的元素，然后将其存储到哈希表中；
  • 再遍历一遍 nums1，从哈希表中取出对应结果，存放到答案数组中；
  • 这种解法的时间复杂度是 O(n)。

💎 代码

👉 查看代码 👈
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function (nums1, nums2) {
	let map = new Map();
	let stack = [];
	for (let num of nums2) {
		while (stack.length && stack[stack.length - 1] < num) {
			map.set(stack.pop(), num);
		}
		stack.push(num);
	}
	for (let i = 0; i < nums1.length; i++) {
		nums1[i] = map.has(nums1[i]) ? map.get(nums1[i]) : -1;
	}
	return nums1;
};

#### 📌 [496. 下一个更大元素 I - LeetCode](https://2xiao.github.io/leetcode-js/problem/0496.html)

#### 💻 **题目大意**

给定两个没有重复元素的数组 `nums1` 和 `nums2` ，其中 `nums1` 是 `nums2` 的子集。找出 `nums1` 中每个元素在 `nums2` 中的下一个比其大的值。

`nums1` 中数字 `x` 的下一个更大元素是指： `x` 在 `nums2` 中对应位置的右边的第一个比 `x` 大的元素。如果不存在，对应位置输出 `-1`。

请设计一个时间复杂度为 `O(nums1.length + nums2.length)` 的解决方案。

**示例**：

> 输入：nums1 = [4,1,2], nums2 = [1,3,4,2]
>
> 输出：[-1,3,-1]

> 输入：nums1 = [2,4], nums2 = [1,2,3,4]
>
> 输出：[3,-1]

**说明**：

- `1 <= nums1.length <= nums2.length <= 1000`
- `0 <= nums1[i]`, `nums2[i] <= 10^4`
- `nums1` 和 `nums2` 中所有整数互不相同
- `nums1` 中的所有整数同样出现在 `nums2` 中

#### 💡 **解题思路**

- 使用单调递增栈；
- 因为 `nums1` 是 `nums2` 的子集，所以我们可以先遍历一遍 `nums2`，并构造单调递增栈；
- 求出 `nums2` 中每个元素右侧下一个更大的元素，然后将其存储到哈希表中；
- 再遍历一遍 `nums1`，从哈希表中取出对应结果，存放到答案数组中；
- 这种解法的时间复杂度是 `O(n)`。

#### 💎 **代码**

<details>
<summary>👉 查看代码 👈</summary>

```javascript
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function (nums1, nums2) {
	let map = new Map();
	let stack = [];
	for (let num of nums2) {
		while (stack.length && stack[stack.length - 1] < num) {
			map.set(stack.pop(), num);
		}
		stack.push(num);
	}
	for (let i = 0; i < nums1.length; i++) {
		nums1[i] = map.has(nums1[i]) ? map.get(nums1[i]) : -1;
	}
	return nums1;
};
```

</details>

2. 每日温度

相关题目

📌 739. 每日温度 - LeetCodeopen in new window

💻 题目大意

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例：

输入：temperatures = [73,74,75,71,69,72,76,73]

输出：[1,1,4,2,1,1,0,0]

输入：temperatures = [30,40,50,60]

输出：[1,1,1,0]

输入：temperatures = [30,60,90]

输出：[1,1,0]

说明：

  • 1 <= temperatures.length <= 10^5
  • 30 <= temperatures[i] <= 100

💡 解题思路

  • 使用单调递增栈；
  • 先遍历一遍 temperatures，并构造单调递增栈，栈中保存元素对应的 index；
  • 求出 temperatures 中每个元素右侧下一个更大的元素，然后将其对应的 index 存储到哈希表中；
  • 然后再遍历一遍 temperatures，从哈希表中取出对应结果，将差值 value - key 存放到答案数组中；
  • 这种解法的时间复杂度是 O(n)。

💎 代码

👉 查看代码 👈
/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
	let map = new Map();
	let stack = [];
	for (let i = 0; i < temperatures.length; i++) {
		while (
			stack.length &&
			temperatures[stack[stack.length - 1]] < temperatures[i]
		) {
			map.set(stack.pop(), i);
		}
		stack.push(i);
	}
	for (let i = 0; i < temperatures.length; i++) {
		temperatures[i] = map.has(i) ? map.get(i) - i : 0;
	}
	return temperatures;
};

#### 📌 [739. 每日温度 - LeetCode](https://2xiao.github.io/leetcode-js/problem/0739.html)

#### 💻 **题目大意**

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

**示例**：

> 输入：temperatures = [73,74,75,71,69,72,76,73]
>
> 输出：[1,1,4,2,1,1,0,0]

> 输入：temperatures = [30,40,50,60]
>
> 输出：[1,1,1,0]

> 输入：temperatures = [30,60,90]
>
> 输出：[1,1,0]

**说明**：

- `1 <= temperatures.length <= 10^5`
- `30 <= temperatures[i] <= 100`

#### 💡 **解题思路**

- 使用单调递增栈；
- 先遍历一遍 `temperatures`，并构造单调递增栈，栈中保存元素对应的 `index`；
- 求出 `temperatures` 中每个元素右侧下一个更大的元素，然后将其对应的 `index` 存储到哈希表中；
- 然后再遍历一遍 `temperatures`，从哈希表中取出对应结果，将差值 `value - key` 存放到答案数组中；
- 这种解法的时间复杂度是 `O(n)`。

#### 💎 **代码**

<details>
<summary>👉 查看代码 👈</summary>

```javascript
/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
	let map = new Map();
	let stack = [];
	for (let i = 0; i < temperatures.length; i++) {
		while (
			stack.length &&
			temperatures[stack[stack.length - 1]] < temperatures[i]
		) {
			map.set(stack.pop(), i);
		}
		stack.push(i);
	}
	for (let i = 0; i < temperatures.length; i++) {
		temperatures[i] = map.has(i) ? map.get(i) - i : 0;
	}
	return temperatures;
};
```

</details>

相关题目

栈基础题目

题号标题题解标签难度力扣
1047删除字符串中的所有相邻重复项[✓]栈 字符串🟢🀄️open in new window 🔗open in new window
155最小栈[✓]栈 设计🟠🀄️open in new window 🔗open in new window
20有效的括号[✓]栈 字符串🟢🀄️open in new window 🔗open in new window
227基本计算器 II[✓]栈 数学 字符串🟠🀄️open in new window 🔗open in new window
739每日温度[✓]栈 数组 单调栈🟠🀄️open in new window 🔗open in new window
150逆波兰表达式求值[✓]栈 数组 数学🟠🀄️open in new window 🔗open in new window
232用栈实现队列[✓]栈 设计 队列🟢🀄️open in new window 🔗open in new window
剑指 Offer 9用两个栈实现队列[✓]栈 设计 队列🟢🀄️open in new window
394字符串解码[✓]栈 递归 字符串🟠🀄️open in new window 🔗open in new window
32最长有效括号[✓]栈 字符串 动态规划🔴🀄️open in new window 🔗open in new window
946验证栈序列[✓]栈 数组 模拟🟠🀄️open in new window 🔗open in new window
剑指 Offer 6从尾到头打印链表[✓]栈 递归 链表 1+🟢🀄️open in new window
71简化路径[✓]栈 字符串🟠🀄️open in new window 🔗open in new window

单调栈

题号标题题解标签难度力扣
739每日温度[✓]栈 数组 单调栈🟠🀄️open in new window 🔗open in new window
496下一个更大元素 I[✓]栈 数组 哈希表 1+🟢🀄️open in new window 🔗open in new window
503下一个更大元素 II[✓]栈 数组 单调栈🟠🀄️open in new window 🔗open in new window
901股票价格跨度[✓]栈 设计 数据流 1+🟠🀄️open in new window 🔗open in new window
84柱状图中最大的矩形[✓]栈 数组 单调栈🔴🀄️open in new window 🔗open in new window
316去除重复字母[✓]栈 贪心 字符串 1+🟠🀄️open in new window 🔗open in new window
42接雨水[✓]栈 数组 双指针 2+🔴🀄️open in new window 🔗open in new window
85最大矩形[✓]栈 数组 动态规划 2+🔴🀄️open in new window 🔗open in new window
Copyright © 2024 2xiao