LeetCode Go · 栈与队列（2）

返回题库与筛选 · 收录范围与使用说明

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

1106. 解析布尔表达式

困难1 种解法

标签：栈、递归、字符串

题目、示例与约束

布尔表达式 是计算结果不是 true 就是 false 的表达式。有效的表达式需遵循以下约定：

• 't'，运算结果为 true
• 'f'，运算结果为 false
• '!(subExpr)'，运算过程为对内部表达式 subExpr 进行 逻辑非（NOT）运算
• '&(subExpr1, subExpr2, ..., subExprn)'，运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, ..., subExprn 进行 逻辑与（AND）运算
• '|(subExpr1, subExpr2, ..., subExprn)'，运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, ..., subExprn 进行 逻辑或（OR）运算

给你一个以字符串形式表述的 布尔表达式 expression，返回该式的运算结果。

题目测试用例所给出的表达式均为有效的布尔表达式，遵循上述约定。

 

示例 1：

输入：expression = "&(|(f))"
输出：false
解释：
首先，计算 |(f) --> f ，表达式变为 "&(f)" 。
接着，计算 &(f) --> f ，表达式变为 "f" 。
最后，返回 false 。

示例 2：

输入：expression = "|(f,f,f,t)"
输出：true
解释：计算 (false OR false OR false OR true) ，结果为 true 。

示例 3：

输入：expression = "!(&(f,t))"
输出：true
解释：
首先，计算 &(f,t) --> (false AND true) --> false --> f ，表达式变为 "!(f)" 。
接着，计算 !(f) --> NOT false --> true ，返回 true 。

 

提示：

• 1 <= expression.length <= 2 * 104
• expression[i] 为 '('、')'、'&'、'|'、'!'、't'、'f' 和 ',' 之一

方法一：栈 · Go 实现

思考

表达式含嵌套的 !、&、|，递归下降需要处理括号配对与逗号。从左到右扫描时，把 t、f 与算子压栈，遇 ) 则弹出到算子，并按弹出的真假个数归约出新的 t 或 f 再入栈，相当于按括号层次求值。

逗号只作分隔，不必入栈。扫完后栈中只剩一个字符，即为整个表达式的值。

对于这种表达式解析问题，我们可以使用栈来辅助解决。

从左到右遍历表达式 expression，对于遍历到的每个字符 $c$：

• 如果 $c$ 是 "tf!&|" 中的一个，我们直接将其入栈；
• 如果 $c$ 是右括号 ')'，我们将栈中元素依次出栈，直到遇到操作符 '!' 或 '&' 或 '|'。过程中我们用变量 $t$ 和 $f$ 记录出栈字符中 't' 和 'f' 的个数。最后根据出栈字符的个数和操作符计算得到新的字符 't' 或 'f'，并将其入栈。

遍历完表达式 expression 后，栈中只剩下一个字符，如果是 't'，返回 true，否则返回 false。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是表达式 expression 的长度。

func parseBoolExpr(expression string) bool {
	stk := []rune{}
	for _, c := range expression {
		if c != '(' && c != ')' && c != ',' {
			stk = append(stk, c)
		} else if c == ')' {
			var t, f int
			for stk[len(stk)-1] == 't' || stk[len(stk)-1] == 'f' {
				if stk[len(stk)-1] == 't' {
					t++
				} else {
					f++
				}
				stk = stk[:len(stk)-1]
			}
			op := stk[len(stk)-1]
			stk = stk[:len(stk)-1]
			c = 'f'
			if (op == '!' && f > 0) || (op == '&' && f == 0) || (op == '|' && t > 0) {
				c = 't'
			}
			stk = append(stk, c)
		}
	}
	return stk[0] == 't'
}

力扣原题 · Doocs 题解来源

1111. 有效括号的嵌套深度

中等1 种解法

标签：栈、字符串、括号序列

题目、示例与约束

如果一个字符串仅由字符 "(" 和 ")" 组成，并且满足以下条件，则称为有效括号字符串（VPS）：

• 它是空字符串，或
• 它可以表示为 AB（A 连接 B），其中 A 和 B 都是VPS，或者
• 它可以表示为 (A)，其中 A 是一个 VPS。

我们可以类似地定义任何 VPS S 的嵌套深度 depth(S) 如下：

• depth("") = 0
• depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 VPS
• depth("(" + A + ")") = 1 + depth(A)，其中 A 是一个 VPS。

例如，""，"()()" 和 "()(()())" 都是 VPS（嵌套深度 0，1 和 2），并且 ")(" 和 "(()" 不是 VPS。

给定一个 VPS 序列，将其拆分成两个不相交的子序列 A 和 B，使得 A 和 B 都是 VPS（且 A.length + B.length = seq.length）。这些子序列不一定是连续的。

例如，对于序列 123456789，一种可能的拆分是：

• A = {1, 3, 5, 7, 9}，

• B = {2, 4, 6, 8}。

• 这对应于输出 [0, 1, 0, 1, 0, 1, 0, 1, 0]，其中 0 表示属于 A，1 表示属于 B。

现在选择 任意 这样的 A 和 B，使得 max(depth(A), depth(B)) 的值是最小的。

返回一个 answer 数组（长度为 seq.length），该数组编码了 A 和 B 的选择：如果 seq[i] 是 A 的一部分则 answer[i] = 0，否则 answer[i] = 1。请注意，尽管可能存在多种答案，但你可以返回其中任意一种。

 

示例 1：

输入：seq = "(()())"
输出：[0,1,1,1,1,0]

示例 2：

输入：seq = "()(())()"
输出：[0,0,0,1,1,0,1,1]
解释：本示例答案不唯一。
按此输出 A = "()()", B = "()()", max(depth(A), depth(B)) = 1，它们的深度最小。
像 [1,1,1,0,0,1,1,1]，也是正确结果，其中 A = "()()()", B = "()", max(depth(A), depth(B)) = 1 。 

 

提示：

• 1 < seq.size <= 10000

 

有效括号字符串：

仅由 "(" 和 ")" 构成的字符串，对于每个左括号，都能找到与之对应的右括号，反之亦然。
下述几种情况同样属于有效括号字符串：

  1. 空字符串
  2. 连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串
  3. 嵌套，可以记作 (A)，其中 A 是有效括号字符串

嵌套深度：

类似地，我们可以定义任意有效括号字符串 s 的 嵌套深度 depth(S)：

  1. s 为空时，depth("") = 0
  2. s 为 A 与 B 连接时，depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是有效括号字符串
  3. s 为嵌套情况，depth("(" + A + ")") = 1 + depth(A)，其中 A 是有效括号字符串

例如：""，"()()"，和 "()(()())" 都是有效括号字符串，嵌套深度分别为 0，1，2，而 ")(" 和 "(()" 都不是有效括号字符串。

方法一：贪心 · Go 实现

思考

每个括号都要指定组别，再检查两组是否都合法。 $n\le {10}^4$，把每个位置的组别枚举一遍并不现实。改成贪心也可以：左括号分给当前较浅的一组，右括号跟回同一组。这样做是对的，但扫描时要同时记下两组的深度。

深度是沿嵌套一层层加上去的。一条深度为 $d$ 的链有 $d$ 层，分给两组之后，其中一组至少分到 $\lceil d/2\rceil$ 层。把相邻层交错开，两组的深度就分别是 $\lceil d/2\rceil$ 和 $\lfloor d/2\rfloor$。

组号取层号的奇偶就够了，只留一个平衡度 $x$。左括号落在即将进入的那一层，要看加深之前的 $x$；右括号得跟着配对的左括号走，要看回退之后的 $x$。同一对括号读到的奇偶相同，拆出来的两个子序列仍然合法。

我们用变量 $x$ 记录当前的平衡度，也就是尚未匹配的左括号个数，它同时也是当前位置的嵌套深度。

从左到右扫描 $seq$。遇到左括号，先把 $x$ 的奇偶写入答案，偶数为 $0$、奇数为 $1$，然后 $x$ 加一。遇到右括号，先将 $x$ 减一，再按新的奇偶写入答案。匹配的一对括号读到同一个奇偶，进入同一组，因此两组都仍然是合法括号串。设原串嵌套深度为 $d$，两组深度的最大值等于 $\lceil d/2\rceil$。

时间复杂度 $O(n)$，其中 $n$ 是字符串 $seq$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

func maxDepthAfterSplit(seq string) []int {
	n := len(seq)
	ans := make([]int, n)
	for i, x := 0, 0; i < n; i++ {
		if seq[i] == '(' {
			ans[i] = x & 1
			x++
		} else {
			x--
			ans[i] = x & 1
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1124. 表现良好的最长时间段

中等1 种解法

标签：栈、数组、哈希表、前缀和、单调栈

题目、示例与约束

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。

我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。

所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。

请你返回「表现良好时间段」的最大长度。

 

示例 1：

输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。

示例 2：

输入：hours = [6,6,6]
输出：0

 

提示：

• 1 <= hours.length <= 104
• 0 <= hours[i] <= 16

方法一：前缀和 + 哈希表 · Go 实现

思考

把 $>8$ 记为 $+1$，否则 $-1$，区间劳累日更多当且仅当前缀和 $s_j-s_i>0$。枚举所有 $(i,j)$ 为平方级。

$s>0$ 时从起点到当前位置整段合法；否则只需找到更早出现的 $s-1$，使区间和恰为 $1$。哈希表记录每个前缀和首次下标，保证区间尽量长。

我们可以利用前缀和的思想，维护一个变量 $s$，表示从下标 $0$ 到当前下标的这一段，「劳累的天数」与「不劳累的天数」的差值。如果 $s$ 大于 $0$，说明从下标 $0$ 到当前下标的这一段，满足「表现良好的时间段」。另外，用哈希表 $pos$ 记录每个 $s$ 第一次出现的下标。

接下来，我们遍历数组 hours，对于每个下标 $i$：

• 如果 $hours[i]>8$，我们就让 $s$ 加 $1$，否则减 $1$。
• 如果 $s$ 大于 $0$，说明从下标 $0$ 到当前下标的这一段，满足「表现良好的时间段」，我们更新结果 $ans=i+1$。否则，如果 $s-1$ 在哈希表 $pos$ 中，记 $j=pos[s-1]$，说明从下标 $j+1$ 到当前下标 $i$ 的这一段，满足「表现良好的时间段」，我们更新结果 $ans=max(ans,i-j)$。
• 然后，如果 $s$ 不在哈希表 $pos$ 中，我们就记录 $pos[s]=i$。

遍历结束后，返回答案即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 hours 的长度。

func longestWPI(hours []int) (ans int) {
	s := 0
	pos := map[int]int{}
	for i, x := range hours {
		if x > 8 {
			s++
		} else {
			s--
		}
		if s > 0 {
			ans = i + 1
		} else if j, ok := pos[s-1]; ok {
			ans = max(ans, i-j)
		}
		if _, ok := pos[s]; !ok {
			pos[s] = i
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1190. 反转每对括号间的子串

中等2 种解法

标签：栈、字符串、括号序列

题目、示例与约束

给出一个字符串 s（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，您的结果中 不应 包含任何括号。

 

示例 1：

输入：s = "(abcd)"
输出："dcba"

示例 2：

输入：s = "(u(love)i)"
输出："iloveu"
解释：先反转子字符串 "love" ，然后反转整个字符串。

示例 3：

输入：s = "(ed(et(oc))el)"
输出："leetcode"
解释：先反转子字符串 "oc" ，接着反转 "etco" ，然后反转整个字符串。

 

提示：

• 1 <= s.length <= 2000
• s 中只有小写英文字母和括号
• 题目测试用例确保所有括号都是成对出现的

方法一：模拟 · Go 实现

思考

括号从内向外反转，可用栈模拟：遇 ) 则弹出至配对 (，倒序再压回。每层反转可能移动 $O(n)$ 个字符，最坏 $O(n^2)$，但 $n\le 2000$ 可接受。

我们可以直接用栈来模拟反转的过程。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。

func reverseParentheses(s string) string {
	stk := []byte{}
	for i := range s {
		if s[i] == ')' {
			t := []byte{}
			for stk[len(stk)-1] != '(' {
				t = append(t, stk[len(stk)-1])
				stk = stk[:len(stk)-1]
			}
			stk = stk[:len(stk)-1]
			stk = append(stk, t...)
		} else {
			stk = append(stk, s[i])
		}
	}
	return string(stk)
}

方法二：脑筋急转弯 · Go 实现

思考

方法一反复搬动字符。配对括号相当于「跳到对端并掉头」：预处理每对括号的下标，遍历时遇括号则跳转并取反步长，只把字母写入答案，线性扫完。

我们观察发现，遍历字符串时，每一次遇到 ( 或者 )，都是跳到对应的 ) 或者 (，然后反转遍历的方向，继续遍历。

因此，我们可以用一个数组 $d$ 来记录每个 ( 或者 ) 对应的另一个括号的位置，即 $d[i]$ 表示 $i$ 处的括号对应的另一个括号的位置。直接用栈就可以求出 $d$ 数组。

然后，我们从左到右遍历字符串，遇到 ( 或者 ) 时，根据 $d$ 数组跳到对应的位置，然后反转方向，继续遍历，直到遍历完整个字符串。

时间复杂度 $O(n)$，空间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。

func reverseParentheses(s string) string {
	n := len(s)
	d := make([]int, n)
	stk := []int{}
	for i, c := range s {
		if c == '(' {
			stk = append(stk, i)
		} else if c == ')' {
			j := stk[len(stk)-1]
			stk = stk[:len(stk)-1]
			d[i], d[j] = j, i
		}
	}
	ans := []byte{}
	i, x := 0, 1
	for i < n {
		if s[i] == '(' || s[i] == ')' {
			i = d[i]
			x = -x
		} else {
			ans = append(ans, s[i])
		}
		i += x
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

1209. 删除字符串中的所有相邻重复项 II

中等1 种解法

标签：栈、字符串

题目、示例与约束

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

本题答案保证唯一。

 

示例 1：

输入：s = "abcd", k = 2
输出："abcd"
解释：没有要删除的内容。

示例 2：

输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释： 
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"

示例 3：

输入：s = "pbbcggttciiippooaais", k = 2
输出："ps"

 

提示：

• 1 <= s.length <= 10^5
• 2 <= k <= 10^4
• s 中只含有小写英文字母。

方法一：栈 · Go 实现

思考

反复扫描删除连续 $k$ 个相同字符， $n\le {10}^5$ 时最坏会多次重扫。删除具有局部性：只有相邻的相同字符会合并，且删除后两侧可能再相遇。

栈按从左到右的顺序保存尚未消除的字符及其连续次数。当前字符与栈顶相同则累加；次数达到 $k$ 则整段弹出，相当于一次消除。

为此栈中存 $(\mathrm{字}\mathrm{符},\mathrm{次}\mathrm{数})$，入栈时对 $k$ 取模以便刚好满 $k$ 时弹出。一遍扫描后栈内剩余即最终串。

我们可以遍历字符串 $s$，维护一个栈，栈中存储的是字符和该字符出现的次数。当遍历到字符 $c$ 时，如果栈顶元素的字符和 $c$ 相同，则将栈顶元素的次数加一，否则将字符 $c$ 和次数 $1$ 入栈。当栈顶元素的次数等于 $k$ 时，将栈顶元素出栈。

遍历完字符串 $s$ 后，栈中存储的就是最终结果。我们可以将栈中的元素依次弹出，拼接成字符串即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $s$ 的长度。

func removeDuplicates(s string, k int) string {
	stk := []pair{}
	for _, c := range s {
		if len(stk) > 0 && stk[len(stk)-1].c == c {
			stk[len(stk)-1].v = (stk[len(stk)-1].v + 1) % k
			if stk[len(stk)-1].v == 0 {
				stk = stk[:len(stk)-1]
			}
		} else {
			stk = append(stk, pair{c, 1})
		}
	}
	ans := []rune{}
	for _, e := range stk {
		for i := 0; i < e.v; i++ {
			ans = append(ans, e.c)
		}
	}
	return string(ans)
}

type pair struct {
	c rune
	v int
}

力扣原题 · Doocs 题解来源

1249. 移除无效的括号

中等1 种解法

标签：栈、字符串

题目、示例与约束

给你一个由 '('、')' 和小写字母组成的字符串 s。

你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

请返回任意一个合法字符串。

有效「括号字符串」应当符合以下 任意一条 要求：

• 空字符串或只包含小写字母的字符串
• 可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
• 可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

 

示例 1：

输入：s = "lee(t(c)o)de)"
输出："lee(t(c)o)de"
解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。

示例 2：

输入：s = "a)b(c)d"
输出："ab(c)d"

示例 3：

输入：s = "))(("
输出：""
解释：空字符串也是有效的

 

提示：

• 1 <= s.length <= 105
• s[i] 可能是 '('、')' 或英文小写字母

方法一：两遍扫描 · Go 实现

思考

要删最少括号使剩余串合法， $n\le {10}^5$。栈匹配可以标出所有非法括号，但也可以用计数器分向扫描：从左向右丢掉无法匹配的右括号，再从右向左丢掉多余左括号。

第一遍保证前缀中右括号从不超过左括号；第二遍对称处理左括号。两遍后剩余括号可一一匹配，字母原样保留。

我们先从左向右扫描，将多余的右括号删除，再从右向左扫描，将多余的左括号删除。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是字符串 $s$ 的长度。

相似题目：

• 678. 有效的括号字符串
• 2116. 判断一个括号字符串是否有效

func minRemoveToMakeValid(s string) string {
	stk := []byte{}
	x := 0
	for i := range s {
		c := s[i]
		if c == ')' && x == 0 {
			continue
		}
		if c == '(' {
			x++
		} else if c == ')' {
			x--
		}
		stk = append(stk, c)
	}
	ans := []byte{}
	x = 0
	for i := len(stk) - 1; i >= 0; i-- {
		c := stk[i]
		if c == '(' && x == 0 {
			continue
		}
		if c == ')' {
			x++
		} else if c == '(' {
			x--
		}
		ans = append(ans, c)
	}
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

1441. 用栈操作构建数组

中等1 种解法

标签：栈、数组、模拟

题目、示例与约束

给你一个数组 target 和一个整数 n。

给你一个空栈和两种操作：

• "Push"：将一个整数加到栈顶。
• "Pop"：从栈顶删除一个整数。

同时给定一个范围 [1, n] 中的整数流。

使用两个栈操作使栈中的数字（从底部到顶部）等于 target。你应该遵循以下规则：

• 如果整数流不为空，从流中选取下一个整数并将其推送到栈顶。
• 如果栈不为空，弹出栈顶的整数。
• 如果，在任何时刻，栈中的元素（从底部到顶部）等于 target，则不要从流中读取新的整数，也不要对栈进行更多操作。

请返回遵循上述规则构建 target 所用的操作序列。如果存在多个合法答案，返回 任一 即可。

 

示例 1：

输入：target = [1,3], n = 3
输出：["Push","Push","Pop","Push"]
解释：一开始栈为空。最后一个元素是栈顶。
从流中读取 1 并推入数组。s = [1]。
从流中读取 2 并推入数组。s = [1,2]。
从栈顶删除整数。s = [1]。
从流中读取 3 并推入数组。s = [1,3]。

示例 2：

输入：target = [1,2,3], n = 3
输出：["Push","Push","Push"]
解释：一开始栈为空。最后一个元素是栈顶。
从流中读取 1 并推入数组。s = [1]。
从流中读取 2 并推入数组。s = [1,2]。
从流中读取 3 并推入数组。s = [1,2,3]。

示例 3：

输入：target = [1,2], n = 4
输出：["Push","Push"]
解释：一开始栈为空。最后一个元素是栈顶。
从流中读取 1 并推入数组。s = [1]。
从流中读取 2 并推入数组。s = [1,2]。
由于栈（从底部到顶部）等于 target，我们停止栈操作。
从流中读取整数 3 的答案不被接受。

 

提示：

• 1 <= target.length <= 100
• 1 <= n <= 100
• 1 <= target[i] <= n
• target 严格递增

方法一：模拟 · Go 实现

思考

流是 $1,2,\dots ,n$，target 严格递增。对 target 中未出现的数必须 Push 再立刻 Pop，出现的数只 Push。

用指针 $\mathit{\text{cur}}$ 表示下一个读入的数，对每个目标值 $x$，先把空隙填成 Push/Pop，再 Push $x$。 $n\le 100$，模拟即可。

我们定义一个变量 $\mathit{\text{cur}}$ 表示当前待读取的数字，初始时 $\mathit{\text{cur}}=1$，用一个数组 $\mathit{\text{ans}}$ 存储答案。

接下来，我们遍历数组 $\mathit{\text{target}}$ 中的每个数字 $x$：

• 如果 $\mathit{\text{cur}}<x$，我们将 $\mathit{\text{Push}}$ 和 $\mathit{\text{Pop}}$ 依次加入答案，直到 $\mathit{\text{cur}}=x$；
• 然后我们将 $\mathit{\text{Push}}$ 加入答案，表示读取数字 $x$；
• 接着，我们将 $\mathit{\text{cur}}$ 加一，继续处理下一个数字。

遍历结束后，返回答案数组即可。

时间复杂度 $O(n)$，其中 $n$ 是数组 $\mathit{\text{target}}$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

func buildArray(target []int, n int) (ans []string) {
	cur := 1
	for _, x := range target {
		for ; cur < x; cur++ {
			ans = append(ans, "Push", "Pop")
		}
		ans = append(ans, "Push")
		cur++
	}
	return
}

力扣原题 · Doocs 题解来源

1475. 商品折扣后的最终价格

简单1 种解法

标签：栈、数组、单调栈

题目、示例与约束

给你一个数组 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 <= 500
• 1 <= prices[i] <= 10^3

方法一：单调栈 · Go 实现

思考

折扣是右侧第一个不超过当前价格的值。 $n\le 500$ 可双重循环，单调栈可在线性时间内找「下一个更小或相等」。从右往左维护递增栈，栈顶即折扣，就地改写。

题目实际上是求每个元素右侧第一个比它小的元素，可以使用单调栈来解决。

我们逆序遍历数组 $\mathit{\text{prices}}$，利用单调栈找出左侧最近一个比当前元素小的元素，然后计算折扣。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $\mathit{\text{prices}}$ 的长度。

func finalPrices(prices []int) []int {
	stk := []int{}
	for i := len(prices) - 1; i >= 0; i-- {
		x := prices[i]
		for len(stk) > 0 && stk[len(stk)-1] > x {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			prices[i] -= stk[len(stk)-1]
		}
		stk = append(stk, x)
	}
	return prices
}

力扣原题 · Doocs 题解来源

1544. 整理字符串

简单1 种解法

标签：栈、字符串

题目、示例与约束

给你一个由大小写英文字母组成的字符串 s 。

一个整理好的字符串中，两个相邻字符 s[i] 和 s[i+1]，其中 0<= i <= s.length-2 ，要满足如下条件:

• 若 s[i] 是小写字符，则 s[i+1] 不可以是相同的大写字符。
• 若 s[i] 是大写字符，则 s[i+1] 不可以是相同的小写字符。

请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除，直到字符串整理好为止。

请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。

注意：空字符串也属于整理好的字符串，尽管其中没有任何字符。

 

示例 1：

输入：s = "leEeetcode"
输出："leetcode"
解释：无论你第一次选的是 i = 1 还是 i = 2，都会使 "leEeetcode" 缩减为 "leetcode" 。

示例 2：

输入：s = "abBAcC"
输出：""
解释：存在多种不同情况，但所有的情况都会导致相同的结果。例如：
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

示例 3：

输入：s = "s"
输出："s"

 

提示：

• 1 <= s.length <= 100
• s 只包含小写和大写英文字母

方法一：栈模拟 · Go 实现

思考

整理好的串不含相邻的大小写同一字母。反复从左扫描删除在 $n\le 100$ 时可行，但一次删除可能让更早的一对撞上，需要来回走。

栈保存当前已整理前缀：新字符若与栈顶相差 $32$（恰为一对大小写），则弹出栈顶，相当于删掉这一对；否则入栈。线性扫完即得结果。

时间复杂度 $O(n)$，空间复杂度 $O(n)$，其中 $n$ 是字符串 s 的长度。

func makeGood(s string) string {
	stk := []rune{}
	for _, c := range s {
		if len(stk) == 0 || abs(int(stk[len(stk)-1]-c)) != 32 {
			stk = append(stk, c)
		} else {
			stk = stk[:len(stk)-1]
		}
	}
	return string(stk)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

1598. 文件夹操作日志搜集器

简单1 种解法

标签：栈、数组、字符串

题目、示例与约束

每当用户执行变更文件夹操作时，LeetCode 文件系统都会保存一条日志记录。

下面给出对变更操作的说明：

• "../" ：移动到当前文件夹的父文件夹。如果已经在主文件夹下，则 继续停留在当前文件夹 。
• "./" ：继续停留在当前文件夹。
• "x/" ：移动到名为 x 的子文件夹中。题目数据 保证总是存在文件夹 x 。

给你一个字符串列表 logs ，其中 logs[i] 是用户在 ith 步执行的操作。

文件系统启动时位于主文件夹，然后执行 logs 中的操作。

执行完所有变更文件夹操作后，请你找出 返回主文件夹所需的最小步数 。

 

示例 1：

输入：logs = ["d1/","d2/","../","d21/","./"]
输出：2
解释：执行 "../" 操作变更文件夹 2 次，即可回到主文件夹

示例 2：

输入：logs = ["d1/","d2/","./","d3/","../","d31/"]
输出：3

示例 3：

输入：logs = ["d1/","../","../","../"]
输出：0

 

提示：

• 1 <= logs.length <= 103
• 2 <= logs[i].length <= 10
• logs[i] 包含小写英文字母，数字，'.' 和 '/'
• logs[i] 符合语句中描述的格式
• 文件夹名称由小写英文字母和数字组成

方法一：模拟 · Go 实现

思考

日志表示进入子目录、停留或返回上一级，求回到根所需的最少 $../$ 次数。日志至多 ${10}^3$ 条，模拟当前深度即可，不必维护真实路径栈。

遇到非 $\mathtt{\text{./}}$ 的目录名深度加一； $\mathtt{\text{../}}$ 则深度与 $0$ 取最大后减一。最终深度就是还需要返回的步数。

直接模拟，记录深度的变化即可。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为 logs 的长度。

func minOperations(logs []string) int {
	ans := 0
	for _, v := range logs {
		if v == "../" {
			if ans > 0 {
				ans--
			}
		} else if v[0] != '.' {
			ans++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1614. 括号的最大嵌套深度

简单1 种解法

标签：栈、字符串、括号序列

题目、示例与约束

给定 有效括号字符串 s，返回 s 的 嵌套深度。嵌套深度是嵌套括号的 最大 数量。

 

示例 1：

输入：s = "(1+(2*3)+((8)/4))+1"

输出：3

解释：数字 8 在嵌套的 3 层括号中。

示例 2：

输入：s = "(1)+((2))+(((3)))"

输出：3

解释：数字 3 在嵌套的 3 层括号中。

示例 3：

输入：s = "()(())((()()))"

输出：3

 

提示：

• 1 <= s.length <= 100
• s 由数字 0-9 和字符 '+'、'-'、'*'、'/'、'('、')' 组成
• 题目数据保证括号字符串 s 是 有效的括号字符串

方法一：遍历 · Go 实现

思考

字符串保证合法且长度不超过 $100$，嵌套深度就是扫描过程中未匹配左括号的个数的最大值。

数字与四则运算符不影响深度，只需处理括号。

用变量 $d$ 遇 ( 加一并更新答案，遇 ) 减一，一遍扫描即可。

我们用一个变量 $d$ 记录当前的深度，初始时 $d=0$。

遍历字符串 $s$，当遇到左括号时，深度 $d$ 加一，同时更新答案为当前深度 $d$ 和答案的最大值。当遇到右括号时，深度 $d$ 减一。

最后返回答案即可。

时间复杂度 $O(n)$，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(1)$。

func maxDepth(s string) (ans int) {
	d := 0
	for _, c := range s {
		if c == '(' {
			d++
			ans = max(ans, d)
		} else if c == ')' {
			d--
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1700. 无法吃午餐的学生数量

简单1 种解法

标签：栈、队列、数组、模拟

题目、示例与约束

学校的自助午餐提供圆形和方形的三明治，分别用数字 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 <= 100
• students.length == sandwiches.length
• sandwiches[i] 要么是 0 ，要么是 1 。
• students[i] 要么是 0 ，要么是 1 。

方法一：计数 · Go 实现

思考

若用队列模拟学生轮转，每次比较队首与栈顶，不匹配则把学生送到队尾，最坏情况下每人反复绕圈，实现冗长且依赖顺序。

注意到三明治顺序固定、学生可以任意调位：一旦栈顶种类在剩余学生中为零，后续三明治都无法被取走。因此只需统计两种喜好的人数，再按三明治顺序消耗计数。

当 $cnt[v]=0$ 时，剩余学生全部偏好另一种三明治，即 $cnt[v\oplus 1]$。线性扫完即可得到无法用餐的人数。

我们观察发现，学生位置可调整，而三明治位置不可调整。也就是说，若前面的三明治没被拿走，则往后的所有三明治也无法被拿走。

因此，我们先用计数器 $cnt$ 统计学生喜欢的三明治种类和对应的数量。

然后遍历三明治，若在 $cnt$ 中找不到喜欢此三明治的学生，说明后面的三明治也无法被拿走，返回当前剩余的学生数量。

遍历结束。，说明所有学生都有三明治吃，返回 $0$。

时间复杂度 $O(n)$，其中 $n$ 为三明治数量。空间复杂度 $O(1)$。

func countStudents(students []int, sandwiches []int) int {
	cnt := [2]int{}
	for _, v := range students {
		cnt[v]++
	}
	for _, v := range sandwiches {
		if cnt[v] == 0 {
			return cnt[v^1]
		}
		cnt[v]--
	}
	return 0
}

力扣原题 · Doocs 题解来源

1762. 能看到海景的建筑物 🔒

中等1 种解法

标签：栈、数组、单调栈

题目、示例与约束

有 n 座建筑物。给你一个大小为 n 的整数数组 heights 表示每一个建筑物的高度。

建筑物的右边是海洋。如果建筑物可以无障碍地看到海洋，则建筑物能看到海景。确切地说，如果一座建筑物右边的所有建筑都比它 矮 时，就认为它能看到海景。

返回能看到海景建筑物的下标列表（下标 从 0 开始 ），并按升序排列。

 

示例 1：

输入：heights = [4,2,3,1]
输出：[0,2,3]
解释：1 号建筑物看不到海景，因为 2 号建筑物比它高

示例 2：

输入：heights = [4,3,2,1]
输出：[0,1,2,3]
解释：所有的建筑物都能看到海景。

示例 3：

输入：heights = [1,3,2,4]
输出：[3]
解释：只有 3 号建筑物能看到海景。

示例 4：

输入：heights = [2,2,2,2]
输出：[3]
解释：如果建筑物右边有相同高度的建筑物则无法看到海景。

 

提示：

• 1 <= heights.length <= 105
• 1 <= heights[i] <= 109

方法一：逆序遍历求右侧最大值 · Go 实现

思考

能看到海的楼要求右侧（海侧）没有不低于它的楼。从右往左扫，维护右侧最大值即可。

若当前高度大于 $mx$，则该下标入答案并更新 $mx$。最后把收集到的下标反转为从左到右。

我们逆序遍历数组 $\mathit{\text{height}}$ 每个元素 $v$，判断 $v$ 与右侧最大元素 $mx$ 的大小关系，若 $mx<v$，说明右侧所有元素都比当前元素小，当前位置能看到海景，加入结果数组 $\mathit{\text{ans}}$。然后我们更新 $mx$ 为 $v$。

遍历结束后，逆序返回 $\mathit{\text{ans}}$ 即可。

时间复杂度 $O(n)$，其中 $n$ 为数组长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

func findBuildings(heights []int) (ans []int) {
	mx := 0
	for i := len(heights) - 1; i >= 0; i-- {
		if v := heights[i]; v > mx {
			ans = append(ans, i)
			mx = v
		}
	}
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return
}

力扣原题 · Doocs 题解来源

1776. 车队 II

困难1 种解法

标签：栈、数组、数学、单调栈、堆（优先队列）

题目、示例与约束

在一条单车道上有 n 辆车，它们朝着同样的方向行驶。给你一个长度为 n 的数组 cars ，其中 cars[i] = [positioni, speedi] ，它表示：

• positioni 是第 i 辆车和道路起点之间的距离（单位：米）。题目保证 positioni < positioni+1 。
• speedi 是第 i 辆车的初始速度（单位：米/秒）。

简单起见，所有车子可以视为在数轴上移动的点。当两辆车占据同一个位置时，我们称它们相遇了。一旦两辆车相遇，它们会合并成一个车队，这个车队里的车有着同样的位置和相同的速度，速度为这个车队里 最慢 一辆车的速度。

请你返回一个数组 answer ，其中 answer[i] 是第 i 辆车与下一辆车相遇的时间（单位：秒），如果这辆车不会与下一辆车相遇，则 answer[i] 为 -1 。答案精度误差需在 10-5 以内。

 

示例 1：

输入：cars = [[1,2],[2,1],[4,3],[7,2]]
输出：[1.00000,-1.00000,3.00000,-1.00000]
解释：经过恰好 1 秒以后，第一辆车会与第二辆车相遇，并形成一个 1 m/s 的车队。经过恰好 3 秒以后，第三辆车会与第四辆车相遇，并形成一个 2 m/s 的车队。

示例 2：

输入：cars = [[3,4],[5,4],[6,3],[9,1]]
输出：[2.00000,1.00000,1.50000,-1.00000]

 

提示：

• 1 <= cars.length <= 105
• 1 <= positioni, speedi <= 106
• positioni < positioni+1

方法一：栈 · Go 实现

思考

车向右开，追上右车后并入更慢的车队。一辆车与谁相撞只取决于它右边的车。 $n$ 较大，需线性结构。

从右往左维护「右边尚未被更慢车消化」的候选栈。栈顶比当前车慢才可能被追上；若相撞时刻晚于栈顶自己再相撞的时刻，则栈顶会先消失，应弹出。

弹出后若栈空则永不追及，否则记录与栈顶的相撞时刻并把当前车入栈。

由于每一辆车最终追上其右边第一辆车的时间与其左边的车没有关系，因此，我们可以从右往左遍历，计算每辆车与其右边第一辆车相遇的时间。

具体地，我们维护一个栈，栈中存放的是车辆的编号，栈顶元素表示当前最慢的车辆编号，栈底元素表示当前最快的车辆编号。

当我们遍历到第 $i$ 辆车时，如果第 $i$ 辆车的速度大于栈顶元素对应的车辆 $j$ 的速度，此时我们计算两车相遇的时间，记为 $t$。如果车辆 $j$ 与右边车辆不会相遇，或者 $t$ 小于等于 $j$ 与右辆车相遇的时间，说明车辆 $i$ 可以在 $t$ 时间追上车辆 $j$，更新答案。否则，说明车辆 $i$ 不会与车辆 $j$ 相遇，我们将车辆 $j$ 出栈，继续判断车辆 $i$ 与栈顶元素对应的车辆相遇的时间。如果栈为空，说明车辆 $i$ 不会与任何车辆相遇，更新答案为 $-1$。最后，将车辆 $i$ 入栈。

遍历完所有车辆后，即可得到答案。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为车辆数量。

func getCollisionTimes(cars [][]int) []float64 {
	n := len(cars)
	ans := make([]float64, n)
	for i := range ans {
		ans[i] = -1.0
	}
	stk := []int{}
	for i := n - 1; i >= 0; i-- {
		for len(stk) > 0 {
			j := stk[len(stk)-1]
			if cars[i][1] > cars[j][1] {
				t := float64(cars[j][0]-cars[i][0]) / float64(cars[i][1]-cars[j][1])
				if ans[j] < 0 || t <= ans[j] {
					ans[i] = t
					break
				}
			}
			stk = stk[:len(stk)-1]
		}
		stk = append(stk, i)
	}
	return ans
}

力扣原题 · Doocs 题解来源

1823. 找出游戏的获胜者

中等1 种解法

标签：递归、队列、数组、数学、模拟

题目、示例与约束

共有 n 名小伙伴一起做游戏。小伙伴们围成一圈，按 顺时针顺序 从 1 到 n 编号。确切地说，从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置，其中 1 <= i < n ，从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。

游戏遵循如下规则：

1. 从第 1 名小伙伴所在位置 开始 。
2. 沿着顺时针方向数 k 名小伙伴，计数时需要 包含 起始时的那位小伙伴。逐个绕圈进行计数，一些小伙伴可能会被数过不止一次。
3. 你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏。
4. 如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始，回到步骤 2 继续执行。
5. 否则，圈子中最后一名小伙伴赢得游戏。

给你参与游戏的小伙伴总数 n ，和一个整数 k ，返回游戏的获胜者。

 

示例 1：

输入：n = 5, k = 2
输出：3
解释：游戏运行步骤如下：
1) 从小伙伴 1 开始。
2) 顺时针数 2 名小伙伴，也就是小伙伴 1 和 2 。
3) 小伙伴 2 离开圈子。下一次从小伙伴 3 开始。
4) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 4 。
5) 小伙伴 4 离开圈子。下一次从小伙伴 5 开始。
6) 顺时针数 2 名小伙伴，也就是小伙伴 5 和 1 。
7) 小伙伴 1 离开圈子。下一次从小伙伴 3 开始。
8) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 5 。
9) 小伙伴 5 离开圈子。只剩下小伙伴 3 。所以小伙伴 3 是游戏的获胜者。

示例 2：

输入：n = 6, k = 5
输出：1
解释：小伙伴离开圈子的顺序：5、4、6、2、3 。小伙伴 1 是游戏的获胜者。

 

提示：

• 1 <= k <= n <= 500

 

进阶：你能否使用线性时间复杂度和常数空间复杂度解决此问题？

方法一 · Go 实现

思考

$n$ 个人围成一圈，每次数 $k$ 个淘汰一人，求最后剩下的编号。 $n\le 500$，直接模拟链表或队列可以通过，但每次数 $k$ 步的朴素实现偏慢，也未利用递推结构。

第 $n$ 轮的赢家可由 $n-1$ 人时的赢家推出：在剩下 $n-1$ 人的编号上加 $k$ 再对 $n$ 取模（模 $0$ 视为 $n$）。边界 $n=1$ 时答案为 $1$。按此递推或递归即可 $O(n)$ 求得。

func findTheWinner(n int, k int) int {
	if n == 1 {
		return 1
	}
	ans := (findTheWinner(n-1, k) + k) % n
	if ans == 0 {
		return n
	}
	return ans
}

力扣原题 · Doocs 题解来源

1856. 子数组最小乘积的最大值

中等1 种解法

标签：栈、数组、前缀和、单调栈

题目、示例与约束

一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。

• 比方说，数组 [3,2,5] （最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。

给你一个正整数数组 nums ，请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大，请你返回答案对  109 + 7 取余 的结果。

请注意，最小乘积的最大值考虑的是取余操作 之前 的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。

子数组 定义为一个数组的 连续 部分。

 

示例 1：

输入：nums = [1,2,3,2]
输出：14
解释：最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。
2 * (2+3+2) = 2 * 7 = 14 。

示例 2：

输入：nums = [2,3,3,1,2]
输出：18
解释：最小乘积的最大值由子数组 [3,3] （最小值是 3）得到。
3 * (3+3) = 3 * 6 = 18 。

示例 3：

输入：nums = [3,1,5,6,4,2]
输出：60
解释：最小乘积的最大值由子数组 [5,6,4] （最小值是 4）得到。
4 * (5+6+4) = 4 * 15 = 60 。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 107

方法一：单调栈 + 前缀和 · Go 实现

思考

子数组的最小乘积是其最小值乘以区间和，求全局最大。枚举区间为 $O(n^2)$， $n\le {10}^5$ 无法通过。

每个位置作为最小值时，贡献区间是它向左到第一个更小元素、向右到第一个不更大的元素。单调栈求出左右边界，前缀和在 $O(1)$ 内得到区间和，枚举每个最小值取最大乘积。

我们可以枚举每个元素 $nums[i]$ 作为子数组的最小值，找出子数组的左右边界 $left[i]$ 和 $right[i]$。其中 $left[i]$ 表示 $i$ 左侧第一个严格小于 $nums[i]$ 的位置，而 $right[i]$ 表示 $i$ 右侧第一个小于等于 $nums[i]$ 的位置。

为了方便地算出子数组的和，我们可以预处理出前缀和数组 $s$，其中 $s[i]$ 表示 $nums$ 前 $i$ 个元素的和。

那么以 $nums[i]$ 作为子数组最小值的最小乘积为 $nums[i]\times (s[right[i]]-s[left[i]+1])$。我们可以枚举每个元素 $nums[i]$，求出以 $nums[i]$ 作为子数组最小值的最小乘积，然后取最大值即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。

func maxSumMinProduct(nums []int) int {
	n := len(nums)
	left := make([]int, n)
	right := make([]int, n)
	for i := range left {
		left[i] = -1
		right[i] = n
	}
	stk := []int{}
	for i, x := range nums {
		for len(stk) > 0 && nums[stk[len(stk)-1]] >= x {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			left[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	stk = []int{}
	for i := n - 1; i >= 0; i-- {
		for len(stk) > 0 && nums[stk[len(stk)-1]] > nums[i] {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			right[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	s := make([]int, n+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	ans := 0
	for i, x := range nums {
		if t := x * (s[right[i]] - s[left[i]+1]); ans < t {
			ans = t
		}
	}
	const mod = 1e9 + 7
	return ans % mod
}

力扣原题 · Doocs 题解来源

1910. 删除一个字符串中所有出现的给定子字符串

中等2 种解法

标签：栈、字符串、模拟

题目、示例与约束

给你两个字符串 s 和 part ，请你对 s 反复执行以下操作直到 所有 子字符串 part 都被删除：

• 找到 s 中 最左边 的子字符串 part ，并将它从 s 中删除。

请你返回从 s 中删除所有 part 子字符串以后得到的剩余字符串。

一个 子字符串 是一个字符串中连续的字符序列。

 

示例 1：

输入：s = "daabcbaabcbc", part = "abc"
输出："dab"
解释：以下操作按顺序执行：
- s = "daabcbaabcbc" ，删除下标从 2 开始的 "abc" ，得到 s = "dabaabcbc" 。
- s = "dabaabcbc" ，删除下标从 4 开始的 "abc" ，得到 s = "dababc" 。
- s = "dababc" ，删除下标从 3 开始的 "abc" ，得到 s = "dab" 。
此时 s 中不再含有子字符串 "abc" 。

示例 2：

输入：s = "axxxxyyyyb", part = "xy"
输出："ab"
解释：以下操作按顺序执行：
- s = "axxxxyyyyb" ，删除下标从 4 开始的 "xy" ，得到 s = "axxxyyyb" 。
- s = "axxxyyyb" ，删除下标从 3 开始的 "xy" ，得到 s = "axxyyb" 。
- s = "axxyyb" ，删除下标从 2 开始的 "xy" ，得到 s = "axyb" 。
- s = "axyb" ，删除下标从 1 开始的 "xy" ，得到 s = "ab" 。
此时 s 中不再含有子字符串 "xy" 。

 

提示：

• 1 <= s.length <= 1000
• 1 <= part.length <= 1000
• s​​​​​​ 和 part 只包小写英文字母。

方法一：暴力替换 · Go 实现

思考

$s$ 与 $\mathit{\text{part}}$ 长度分别不超过 ${10}^3$，反复寻找并删除一次出现的代价可接受，不必先构造自动机。

每次用库函数替换最左侧的 $\mathit{\text{part}}$，直到不再出现。删除后可能拼出新的 $\mathit{\text{part}}$，因此必须循环而非只扫一遍。

总长度每次至少缩短 $|\mathit{\text{part}}|$，循环次数有上界，实现与题意一致。

我们循环判断 $s$ 中是否存在字符串 $part$，是则进行一次替换，继续循环此操作，直至 $s$ 中不存在字符串 $part$，返回此时的 $s$ 作为答案字符串。

时间复杂度 $O(n^2+n\times m)$，空间复杂度 $O(n+m)$。其中 $n$ 和 $m$ 分别是字符串 $s$ 和字符串 $part$ 的长度。

func removeOccurrences(s string, part string) string {
	for strings.Contains(s, part) {
		s = strings.Replace(s, part, "", 1)
	}
	return s
}

方法二：栈 · Go 实现

思考

方法一每删掉一次就要重新扫描整串。 $|s|$ 每次至少减少 $1$，轮数可达 $O(n)$，总时间是 $O(n^2)$。

从左往右读时，当前结果里若还有 $\mathit{\text{part}}$，最左侧的那一次一定贴在当前结果的末尾：更早的出现在读到它的时候就已经删掉了。

因此用一个栈保存还没被删掉的字符。每压入一个字符，若末尾的 $m$ 个字符等于 $\mathit{\text{part}}$ 就弹出。一遍扫描即按题意完成所有删除。

用字符串 $st$ 模拟栈，从左到右扫描 $s$。把当前字符追加到 $st$ 末尾；若 $st$ 的长度至少为 $m=|\mathit{\text{part}}|$，且末尾 $m$ 个字符恰好是 $\mathit{\text{part}}$，则删掉这 $m$ 个字符。扫描结束后， $st$ 就是答案。

这样做与方法一等价：任意时刻 $st$ 中都不含 $\mathit{\text{part}}$，下一次能匹配上的 $\mathit{\text{part}}$ 必然以当前字符结尾，也就是剩余字符串中最左侧的一次出现。

时间复杂度 $O(n\times m)$，空间复杂度 $O(n)$。其中 $n$ 和 $m$ 分别是 $s$ 和 $\mathit{\text{part}}$ 的长度。

func removeOccurrences(s string, part string) string {
	m := len(part)
	st := make([]byte, 0, len(s))
	for i := 0; i < len(s); i++ {
		st = append(st, s[i])
		if len(st) >= m && string(st[len(st)-m:]) == part {
			st = st[:len(st)-m]
		}
	}
	return string(st)
}

力扣原题 · Doocs 题解来源

1944. 队列中可以看到的人数

困难1 种解法

标签：栈、数组、单调栈

题目、示例与约束

有 n 个人排成一个队列，从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights ，每个整数 互不相同，heights[i] 表示第 i 个人的高度。

一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮 。更正式的，第 i 个人能看到第 j 个人的条件是 i < j 且 min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]) 。

请你返回一个长度为 n 的数组 answer ，其中 answer[i] 是第 i 个人在他右侧队列中能 看到 的 人数 。

 

示例 1：

输入：heights = [10,6,8,5,11,9]
输出：[3,1,2,1,1,0]
解释：
第 0 个人能看到编号为 1 ，2 和 4 的人。
第 1 个人能看到编号为 2 的人。
第 2 个人能看到编号为 3 和 4 的人。
第 3 个人能看到编号为 4 的人。
第 4 个人能看到编号为 5 的人。
第 5 个人谁也看不到因为他右边没人。

示例 2：

输入：heights = [5,1,2,3,10]
输出：[4,1,1,1,0]

 

提示：

• n == heights.length
• 1 <= n <= 105
• 1 <= heights[i] <= 105
• heights 中所有数 互不相同 。

方法一：单调栈 · Go 实现

思考

$i$ 能看到 $j$，当且仅当中间的人都更矮。对每个 $i$ 向右扫描最坏 $O(n^2)$。

从右向左看， $i$ 右侧可见者高度严格递增。单调栈自栈顶向栈底递增：弹出所有更矮者并计数，若栈仍非空再加一（被更高者挡住）。

每人至多入栈出栈一次，总时间线性。

我们观察发现，对于第 $i$ 个人来说，他能看到的人一定是按从左到右高度严格单调递增的。

因此，我们可以倒序遍历数组 $\mathit{\text{heights}}$，用一个从栈顶到栈底单调递增的栈 $\mathit{\text{stk}}$ 记录已经遍历过的人的高度。

对于第 $i$ 个人，如果栈不为空并且栈顶元素小于 $\mathit{\text{heights}}[i]$，累加当前第 $i$ 个人能看到的人数，然后将栈顶元素出栈，直到栈为空或者栈顶元素大于等于 $\mathit{\text{heights}}[i]$。如果此时栈不为空，说明栈顶元素大于等于 $\mathit{\text{heights}}[i]$，那么第 $i$ 个人能看到的人数还要再加 $1$。

接下来，我们将 $\mathit{\text{heights}}[i]$ 入栈，继续遍历下一个人。

遍历结束后，返回答案数组 $\mathit{\text{ans}}$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $\mathit{\text{heights}}$ 的长度。

相似题目：

• 2282. 在一个网格中可以看到的人数

func canSeePersonsCount(heights []int) []int {
	n := len(heights)
	ans := make([]int, n)
	stk := []int{}
	for i := n - 1; i >= 0; i-- {
		for len(stk) > 0 && stk[len(stk)-1] < heights[i] {
			ans[i]++
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			ans[i]++
		}
		stk = append(stk, heights[i])
	}
	return ans
}

力扣原题 · Doocs 题解来源

1950. 所有子数组最小值中的最大值 🔒

中等1 种解法

标签：栈、数组、单调栈

题目、示例与约束

给你一个长度为 n 的整数数组 nums ，你需要处理 n 个查询。

对于第 i （0 <= i < n）个查询：

1. 你需要先找出 nums 的所有长度为 i + 1 的子数组中的 最小值 。
2. 在这些最小值中找出 最大值 作为答案。

返回一个 下标从 0 开始 的长度为 n 的整数数组 ans ，ans[i] 代表第 i 个查询的答案。

 

示例 1：

输入: nums = [0,1,2,4]
输出: [4,2,1,0]
解释:
i = 0:
- 大小为 1 的子数组为 [0], [1], [2], [4]
- 有最大的最小值的子数组是 [4], 它的最小值是 4
i = 1:
- 大小为 2 的子数组为 [0,1], [1,2], [2,4]
- 有最大的最小值的子数组是 [2,4], 它的最小值是 2
i = 2:
- 大小为 3 的子数组为 [0,1,2], [1,2,4]
- 有最大的最小值的子数组是 [1,2,4], 它的最小值是 1
i = 3:
- 大小为 4 的子数组为 [0,1,2,4]
- 有最大的最小值的子数组是 [0,1,2,4], 它的最小值是 0

示例 2：

输入: nums = [10,20,50,10]
输出: [50,20,10,10]
解释:
i = 0: 
- 大小为 1 的子数组为 [10], [20], [50], [10]
- 有最大的最小值的子数组是 [50], 它的最小值是 50
i = 1: 
- 大小为 2 的子数组为 [10,20], [20,50], [50,10]
- 有最大的最小值的子数组是 [20,50], 它的最小值是 20
i = 2: 
- 大小为 3 的子数组为 [10,20,50], [20,50,10]
- 有最大的最小值的子数组是 [10,20,50], 它的最小值是 10
i = 3: 
- 大小为 4 的子数组为 [10,20,50,10]
- 有最大的最小值的子数组是 [10,20,50,10], 它的最小值是 10

 

提示：

• n == nums.length
• 1 <= n <= 105
• 0 <= nums[i] <= 109

方法一：单调栈 · Go 实现

思考

对每个长度 $k$ 求所有窗口最小值的最大值。滑动窗口最值再取 $max$ 为 $O(n)$ 每个 $k$，总 $O(n^2)$。

以 $nums[i]$ 为最小值的最长区间由其左右严格更小的位置决定，该区间长度 $m$ 意味着 $nums[i]$ 可充当所有 $\le m$ 的答案候选。

单调栈求左右边界，写入 $ans[m-1]$，再从大到小用 $ans[i+1]$ 更新 $ans[i]$，因为更长窗口的最优值也可用于更短窗口。

我们可以先利用单调栈，求出每个位置的左边第一个比它小的位置 $left[i]$ 和右边第一个比它小的位置 $right[i]$，那么以 $nums[i]$ 为最小值的子数组的长度为 $m=right[i]-left[i]-1$。

然后我们遍历数组，对于每个位置 $i$，更新 $ans[m-1]=max(ans[m-1],nums[i])$。

接着我们倒序遍历数组，更新 $ans[i]=max(ans[i],ans[i+1])$。

最后返回 $ans$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组长度。

func findMaximums(nums []int) []int {
	n := len(nums)
	left := make([]int, n)
	right := make([]int, n)
	for i := range left {
		left[i], right[i] = -1, n
	}
	stk := []int{}
	for i, x := range nums {
		for len(stk) > 0 && nums[stk[len(stk)-1]] >= x {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			left[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	stk = []int{}
	for i := n - 1; i >= 0; i-- {
		x := nums[i]
		for len(stk) > 0 && nums[stk[len(stk)-1]] >= x {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			right[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	ans := make([]int, n)
	for i := range ans {
		m := right[i] - left[i] - 1
		ans[m-1] = max(ans[m-1], nums[i])
	}
	for i := n - 2; i >= 0; i-- {
		ans[i] = max(ans[i], ans[i+1])
	}
	return ans
}

力扣原题 · Doocs 题解来源

2073. 买票需要的时间

简单1 种解法

标签：队列、数组、模拟

题目、示例与约束

有 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.length
• 1 <= n <= 100
• 1 <= tickets[i] <= 100
• 0 <= k < n

方法一：一次遍历 · Go 实现

思考

队列循环购票，直接模拟最坏 $O(\sum tickets)$。观察第 $k$ 人买完时：其前面的人至多买 $tickets[k]$ 张，后面的人至多买 $tickets[k]-1$ 张。

对每个人取上述上界与自身需求的较小值再求和，一次遍历即可。

根据题目描述，当第 $k$ 个人完成购票时，在第 $k$ 个人前面的所有人，购买的票数都不会超过第 $k$ 个人购买的票数，而在第 $k$ 个人后面的所有人，购买的票数都不会超过第 $k$ 个人购买的票数减 $1$。

因此，我们可以遍历整个队伍，对于第 $i$ 个人，如果 $i\le k$，购票时间为 $min(\mathit{\text{tickets}}[i],\mathit{\text{tickets}}[k])$，否则购票时间为 $min(\mathit{\text{tickets}}[i],\mathit{\text{tickets}}[k]-1)$。我们将所有人的购票时间相加即可。

时间复杂度 $O(n)$，其中 $n$ 为队伍的长度。空间复杂度 $O(1)$。

func timeRequiredToBuy(tickets []int, k int) (ans int) {
	for i, x := range tickets {
		t := tickets[k]
		if i > k {
			t--
		}
		ans += min(x, t)
	}
	return
}

力扣原题 · Doocs 题解来源

2104. 子数组范围和

中等2 种解法

标签：栈、数组、单调栈

题目、示例与约束

给你一个整数数组 nums 。nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。

返回 nums 中 所有 子数组范围的 和 。

子数组是数组中一个连续 非空 的元素序列。

 

示例 1：

输入：nums = [1,2,3]
输出：4
解释：nums 的 6 个子数组如下所示：
[1]，范围 = 最大 - 最小 = 1 - 1 = 0 
[2]，范围 = 2 - 2 = 0
[3]，范围 = 3 - 3 = 0
[1,2]，范围 = 2 - 1 = 1
[2,3]，范围 = 3 - 2 = 1
[1,2,3]，范围 = 3 - 1 = 2
所有范围的和是 0 + 0 + 0 + 1 + 1 + 2 = 4

示例 2：

输入：nums = [1,3,3]
输出：4
解释：nums 的 6 个子数组如下所示：
[1]，范围 = 最大 - 最小 = 1 - 1 = 0
[3]，范围 = 3 - 3 = 0
[3]，范围 = 3 - 3 = 0
[1,3]，范围 = 3 - 1 = 2
[3,3]，范围 = 3 - 3 = 0
[1,3,3]，范围 = 3 - 1 = 2
所有范围的和是 0 + 0 + 0 + 2 + 0 + 2 = 4

示例 3：

输入：nums = [4,-2,-3,4,1]
输出：59
解释：nums 中所有子数组范围的和是 59

 

提示：

• 1 <= nums.length <= 1000
• -109 <= nums[i] <= 109

 

进阶：你可以设计一种时间复杂度为 O(n) 的解决方案吗？

方法一：暴力枚举 · Go 实现

思考

子数组极差之和等于每个子数组最大值减最小值之和。 $n\le 1000$，枚举左右端点并在扩展时维护当前区间的最大、最小值，时间为 $O(n^2)$，足以通过。

无需对每个区间重新扫描：固定左端 $i$ 后向右推进 $j$，只需用新元素更新 $\mathit{\text{mi}}$、 $\mathit{\text{mx}}$ 并累加差值。

因此双重循环即可得到全部极差之和。

循环遍历 $i$，作为子数组的起始位置。对于每个 $i$，遍历每个 $j$ 作为子数组的终止位置，此过程中不断求解子数组的最大值、最小值，然后累加差值到结果 ans 中。

最后返回 ans 即可。

时间复杂度 $O(n^2)$。

func subArrayRanges(nums []int) int64 {
	var ans int64
	n := len(nums)
	for i := 0; i < n-1; i++ {
		mi, mx := nums[i], nums[i]
		for j := i + 1; j < n; j++ {
			mi = min(mi, nums[j])
			mx = max(mx, nums[j])
			ans += (int64)(mx - mi)
		}
	}
	return ans
}

方法二：单调栈 · Go 实现

思考

方法一在 $n$ 更大时会偏慢。每个元素作为区间最大（或最小）值时，贡献等于它覆盖的子数组个数乘以自身，因而极差之和可改写为「最大贡献减去最小贡献」。

对每个位置，用单调栈求左侧第一个不小于它的位置与右侧第一个更大的位置，即可在线性时间内统计它作为最大值的次数；将数组取相反数再做一次即得最小值贡献。

为此我们实现函数 $f$，分别对原数组与取反数组求和，二者之差即为答案。

枚举每个元素 nums[i] 作为最大值出现在了多少个子数组中，以及作为最小值出现在多少个子数组中。

其中 nums[i] 作为最大值的贡献为正，作为最小值的贡献为负。

我们以 nums[i] 作为最大值为例。找出左侧第一个比 nums[i] 大的位置 left[i]，右侧第一个大于等于 nums[i] 的位置 right[i]。计算每个 nums[i] 的贡献 $(i-left[i])\times (right[i]-i)\times arr[i]$，累加得到结果。

时间复杂度 $O(n)$。

相似题目：

• 907. 子数组的最小值之和

func subArrayRanges(nums []int) int64 {
	f := func(nums []int) int64 {
		stk := []int{}
		n := len(nums)
		left := make([]int, n)
		right := make([]int, n)
		for i := range left {
			left[i] = -1
			right[i] = n
		}
		for i, v := range nums {
			for len(stk) > 0 && nums[stk[len(stk)-1]] <= v {
				stk = stk[:len(stk)-1]
			}
			if len(stk) > 0 {
				left[i] = stk[len(stk)-1]
			}
			stk = append(stk, i)
		}
		stk = []int{}
		for i := n - 1; i >= 0; i-- {
			for len(stk) > 0 && nums[stk[len(stk)-1]] < nums[i] {
				stk = stk[:len(stk)-1]
			}
			if len(stk) > 0 {
				right[i] = stk[len(stk)-1]
			}
			stk = append(stk, i)
		}
		ans := 0
		for i, v := range nums {
			ans += (i - left[i]) * (right[i] - i) * v
		}
		return int64(ans)
	}
	mx := f(nums)
	for i := range nums {
		nums[i] *= -1
	}
	mi := f(nums)
	return mx + mi
}

力扣原题 · Doocs 题解来源

2197. 替换数组中的非互质数

困难1 种解法

标签：栈、数组、数学、最大公约数、数论、最小公倍数

题目、示例与约束

给你一个整数数组 nums 。请你对数组执行下述操作：

1. 从 nums 中找出 任意 两个 相邻 的 非互质 数。
2. 如果不存在这样的数，终止 这一过程。
3. 否则，删除这两个数，并 替换 为它们的 最小公倍数（Least Common Multiple，LCM）。
4. 只要还能找出两个相邻的非互质数就继续 重复 这一过程。

返回修改后得到的 最终 数组。可以证明的是，以 任意 顺序替换相邻的非互质数都可以得到相同的结果。

生成的测试用例可以保证最终数组中的值 小于或者等于 108 。

两个数字 x 和 y 满足 非互质数 的条件是：GCD(x, y) > 1 ，其中 GCD(x, y) 是 x 和 y 的 最大公约数 。

 

示例 1 ：

输入：nums = [6,4,3,2,7,6,2]
输出：[12,7,6]
解释：
- (6, 4) 是一组非互质数，且 LCM(6, 4) = 12 。得到 nums = [12,3,2,7,6,2] 。
- (12, 3) 是一组非互质数，且 LCM(12, 3) = 12 。得到 nums = [12,2,7,6,2] 。
- (12, 2) 是一组非互质数，且 LCM(12, 2) = 12 。得到 nums = [12,7,6,2] 。
- (6, 2) 是一组非互质数，且 LCM(6, 2) = 6 。得到 nums = [12,7,6] 。
现在，nums 中不存在相邻的非互质数。
因此，修改后得到的最终数组是 [12,7,6] 。
注意，存在其他方法可以获得相同的最终数组。

示例 2 ：

输入：nums = [2,2,1,1,3,3,3]
输出：[2,1,1,3]
解释：
- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3,3] 。
- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3] 。
- (2, 2) 是一组非互质数，且 LCM(2, 2) = 2 。得到 nums = [2,1,1,3] 。
现在，nums 中不存在相邻的非互质数。 
因此，修改后得到的最终数组是 [2,1,1,3] 。 
注意，存在其他方法可以获得相同的最终数组。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• 生成的测试用例可以保证最终数组中的值 小于或者等于 108 。

方法一：栈 · Go 实现

思考

相邻不互质则换成它们的 LCM，并继续与两侧合并，直到不能再合。三个数的合并与结合律无关，结果都是 LCM，因而可以只向左合。

栈顶与新来的数若不互质，就弹出并用 LCM 替换栈顶，循环直到互质或栈中不足两个。

每元素至多入出栈一次，中间 $gcd$ 的代价为对数。

如果存在三个相邻的数 $x$, $y$, $z$ 可以进行合并，那么我们先合并 $x$ 和 $y$，再合并 $z$ 的结果，与先合并 $y$ 和 $z$，再合并 $x$ 的结果是一样的，结果均为 $\mathit{\text{LCM}}(x,y,z)$。

因此，我们可以总是优先合并左侧相邻的数，再将合并后的结果与右侧相邻的数进行合并。

我们使用一个栈来模拟这个过程，遍历数组，对于每个数，我们将其入栈，然后不断检查栈顶的两个数是否互质，如果不互质，我们将这两个数出栈，然后将它们的最小公倍数入栈，直到栈顶的两个数互质，或者栈中元素小于两个。

最后栈中的元素即为最终结果。

时间复杂度 $O(n\times \log M)$，空间复杂度 $O(n)$。其中 $M$ 为数组中的最大值。

func replaceNonCoprimes(nums []int) []int {
	stk := []int{}
	for _, x := range nums {
		stk = append(stk, x)
		for len(stk) > 1 {
			x = stk[len(stk)-1]
			y := stk[len(stk)-2]
			g := gcd(x, y)
			if g == 1 {
				break
			}
			stk = stk[:len(stk)-1]
			stk[len(stk)-1] = x * y / g
		}
	}
	return stk
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

力扣原题 · Doocs 题解来源

2211. 统计道路上的碰撞次数

中等1 种解法

标签：栈、字符串、模拟

题目、示例与约束

在一条无限长的公路上有 n 辆汽车正在行驶。汽车按从左到右的顺序按从 0 到 n - 1 编号，每辆车都在一个 独特的 位置。

给你一个下标从 0 开始的字符串 directions ，长度为 n 。directions[i] 可以是 'L'、'R' 或 'S' 分别表示第 i 辆车是向 左 、向 右 或者 停留 在当前位置。每辆车移动时 速度相同 。

碰撞次数可以按下述方式计算：

• 当两辆移动方向 相反 的车相撞时，碰撞次数加 2 。
• 当一辆移动的车和一辆静止的车相撞时，碰撞次数加 1 。

碰撞发生后，涉及的车辆将无法继续移动并停留在碰撞位置。除此之外，汽车不能改变它们的状态或移动方向。

返回在这条道路上发生的 碰撞总次数 。

 

示例 1：

输入：directions = "RLRSLL"
输出：5
解释：
将会在道路上发生的碰撞列出如下：
- 车 0 和车 1 会互相碰撞。由于它们按相反方向移动，碰撞数量变为 0 + 2 = 2 。
- 车 2 和车 3 会互相碰撞。由于 3 是静止的，碰撞数量变为 2 + 1 = 3 。
- 车 3 和车 4 会互相碰撞。由于 3 是静止的，碰撞数量变为 3 + 1 = 4 。
- 车 4 和车 5 会互相碰撞。在车 4 和车 3 碰撞之后，车 4 会待在碰撞位置，接着和车 5 碰撞。碰撞数量变为 4 + 1 = 5 。
因此，将会在道路上发生的碰撞总次数是 5 。

示例 2：

输入：directions = "LLRR"
输出：0
解释：
不存在会发生碰撞的车辆。因此，将会在道路上发生的碰撞总次数是 0 。

 

提示：

• 1 <= directions.length <= 105
• directions[i] 的值为 'L'、'R' 或 'S'

方法一：脑筋急转弯 · Go 实现

思考

相向而行记 $2$ 次碰撞，与静止车相撞记 $1$ 次，最终所有会相遇的车都停下。 $n\le {10}^5$，不宜逐步模拟每对碰撞。

前缀中一直向左开的车左边没有障碍，后缀中一直向右开的车右边没有障碍，这两段永远不会撞上。去掉它们之后，中间剩下的每个非静止车最终都会停下来，各贡献 $1$。

因此先剥去前缀 $\mathtt{\text{L}}$ 与后缀 $\mathtt{\text{R}}$，再统计剩余串中非 $\mathtt{\text{S}}$ 的个数。

根据题意，当两辆移动方向相反的车相撞时，碰撞次数加 $2$，即两辆车被撞停，答案加 $2$；当一辆移动的车和一辆静止的车相撞时，碰撞次数加 $1$，即一辆车被撞停，答案加 $1$。

而显然前缀的 $\mathit{\text{L}}$ 和后缀的 $\mathit{\text{R}}$ 是不会发生碰撞的，所以我们只需要统计中间不等于 $\mathit{\text{S}}$ 的字符个数即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$ 或 $O(1)$。其中 $n$ 是字符串 $\mathit{\text{directions}}$ 的长度。

func countCollisions(directions string) int {
	s := strings.TrimRight(strings.TrimLeft(directions, "L"), "R")
	return len(s) - strings.Count(s, "S")
}

力扣原题 · Doocs 题解来源

2281. 巫师的总力量和

困难1 种解法

标签：栈、数组、前缀和、单调栈

题目、示例与约束

作为国王的统治者，你有一支巫师军队听你指挥。

给你一个下标从 0 开始的整数数组 strength ，其中 strength[i] 表示第 i 位巫师的力量值。对于连续的一组巫师（也就是这些巫师的力量值是 strength 的 子数组），总力量 定义为以下两个值的 乘积 ：

• 巫师中 最弱 的能力值。
• 组中所有巫师的个人力量值 之和 。

请你返回 所有 巫师组的 总 力量之和。由于答案可能很大，请将答案对 109 + 7 取余 后返回。

子数组 是一个数组里 非空 连续子序列。

 

示例 1：

输入：strength = [1,3,1,2]
输出：44
解释：以下是所有连续巫师组：
- [1,3,1,2] 中 [1] ，总力量值为 min([1]) * sum([1]) = 1 * 1 = 1
- [1,3,1,2] 中 [3] ，总力量值为 min([3]) * sum([3]) = 3 * 3 = 9
- [1,3,1,2] 中 [1] ，总力量值为 min([1]) * sum([1]) = 1 * 1 = 1
- [1,3,1,2] 中 [2] ，总力量值为 min([2]) * sum([2]) = 2 * 2 = 4
- [1,3,1,2] 中 [1,3] ，总力量值为 min([1,3]) * sum([1,3]) = 1 * 4 = 4
- [1,3,1,2] 中 [3,1] ，总力量值为 min([3,1]) * sum([3,1]) = 1 * 4 = 4
- [1,3,1,2] 中 [1,2] ，总力量值为 min([1,2]) * sum([1,2]) = 1 * 3 = 3
- [1,3,1,2] 中 [1,3,1] ，总力量值为 min([1,3,1]) * sum([1,3,1]) = 1 * 5 = 5
- [1,3,1,2] 中 [3,1,2] ，总力量值为 min([3,1,2]) * sum([3,1,2]) = 1 * 6 = 6
- [1,3,1,2] 中 [1,3,1,2] ，总力量值为 min([1,3,1,2]) * sum([1,3,1,2]) = 1 * 7 = 7
所有力量值之和为 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44 。

示例 2：

输入：strength = [5,4,6]
输出：213
解释：以下是所有连续巫师组：
- [5,4,6] 中 [5] ，总力量值为 min([5]) * sum([5]) = 5 * 5 = 25
- [5,4,6] 中 [4] ，总力量值为 min([4]) * sum([4]) = 4 * 4 = 16
- [5,4,6] 中 [6] ，总力量值为 min([6]) * sum([6]) = 6 * 6 = 36
- [5,4,6] 中 [5,4] ，总力量值为 min([5,4]) * sum([5,4]) = 4 * 9 = 36
- [5,4,6] 中 [4,6] ，总力量值为 min([4,6]) * sum([4,6]) = 4 * 10 = 40
- [5,4,6] 中 [5,4,6] ，总力量值为 min([5,4,6]) * sum([5,4,6]) = 4 * 15 = 60
所有力量值之和为 25 + 16 + 36 + 36 + 40 + 60 = 213 。

 

提示：

• 1 <= strength.length <= 105
• 1 <= strength[i] <= 109

方法一：单调栈 + 前缀和 · Go 实现

思考

子数组强度是「最小值乘上子数组和」，要求和。 $n\le {10}^5$，枚举子数组不可行。把贡献按最小值位置拆开：对每个 $i$，找到它作为严格最小（左侧大于等于、右侧严格大于）的管辖区间 $[l,r]$，再乘上这些子数组的和的总和。

单调栈求出 $left[i]$、 $right[i]$。子数组和的区间求和可用前缀和的前缀和 $ss$ 在常数时间算：右侧各段和乘左段个数，减去左侧各段和乘右段个数。最后乘 $strength[i]$ 累加取模。

相似题目：

• 907. 子数组的最小值之和

func totalStrength(strength []int) int {
	n := len(strength)
	left := make([]int, n)
	right := make([]int, n)
	for i := range left {
		left[i] = -1
		right[i] = n
	}
	stk := []int{}
	for i, v := range strength {
		for len(stk) > 0 && strength[stk[len(stk)-1]] >= v {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			left[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	stk = []int{}
	for i := n - 1; i >= 0; i-- {
		for len(stk) > 0 && strength[stk[len(stk)-1]] > strength[i] {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			right[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	mod := int(1e9) + 7
	s := make([]int, n+1)
	for i, v := range strength {
		s[i+1] = (s[i] + v) % mod
	}
	ss := make([]int, n+2)
	for i, v := range s {
		ss[i+1] = (ss[i] + v) % mod
	}
	ans := 0
	for i, v := range strength {
		l, r := left[i]+1, right[i]-1
		a := (ss[r+2] - ss[i+1]) * (i - l + 1)
		b := (ss[i+1] - ss[l]) * (r - i + 1)
		ans = (ans + v*((a-b)%mod)) % mod
	}
	return (ans + mod) % mod
}

力扣原题 · Doocs 题解来源

2282. 在一个网格中可以看到的人数 🔒

中等1 种解法

标签：栈、数组、矩阵、单调栈

题目、示例与约束

给定一个 m x n 下标从 0 开始的二维正整数数组 heights，其中 heights[i][j] 是站在位置 (i, j) 上的人的高度。

站在 (row1, col1) 位置的人可以看到站在 (row2, col2) 位置的人，前提是:

• (row2, col2) 的人在 (row1, col1) 的人的右边 或 下面。更正式地说，要么 row1 == row2 时 col1 < col2，要么 row1 < row2 时 col1 == col2。
• 他们中间的人 都 比他们两个矮。

返回一个 m x n 的二维整数数组answer，其中 answer[i][j] 是位于 (i, j) 位置的人可以看到的人数。

 

示例 1:

输入: heights = [[3,1,4,2,5]]
输出: [[2,1,2,1,0]]
解释:
- (0,0) 上的人可以看到 (0,1) 和 (0,2) 的人。
  注意，他看不到 (0,4) 上的人，因为 (0,2) 上的人比他高。
- (0,1) 上的人可以看到 (0,2) 上的人。
- (0,2) 上的人可以看到 (0,3) 和 (0,4) 的人。
- (0,3) 上的人可以看到 (0,4) 上的人。
- (0,4) 上的人看不到任何人。

示例 2:

输入: heights = [[5,1],[3,1],[4,1]]
输出: [[3,1],[2,1],[1,0]]
解释:
- (0,0) 上的人可以看到 (0,1)、(1,0) 和 (2,0) 的人。
- (0,1) 上的人可以看到 (1,1) 上的人。
- (1,0) 上的人可以看到 (1,1) 和 (2,0) 的人。
- (1,1) 上的人可以看到 (2,1) 上的人。
- (2,0) 上的人可以看到 (2,1) 上的人。
- (2,1) 上的人看不到任何人。

 

提示:

• 1 <= heights.length <= 400
• 1 <= heights[i].length <= 400
• 1 <= heights[i][j] <= 105

方法一：单调栈 · Go 实现

思考

每人向右、向下看，视线在严格更高的人处终止，相等者只能看到最近一个。行列独立，与「队列中能看到的人数」相同。从右往左（或从下往上）用单调递减栈即可。

弹栈时统计被挡住的更矮的人；若栈非空再加一（看到下一个不低于自己的人）；再弹出等高的，避免后面重复看见。对每行、每列各做一次后相加。

我们观察发现，对于第 $i$ 个人来说，他能看到的人一定是按从左到右（或者从上到下）高度严格单调递增的。

因此，对于每一行，我们可以用单调栈来求出每个人能看到的人数。

具体地，我们可以倒序遍历数组，用一个从栈顶到栈底单调递增的栈 $stk$ 记录已经遍历过的人的高度。

对于第 $i$ 个人，如果栈不为空并且栈顶元素小于 $heights[i]$，累加当前第 $i$ 个人能看到的人数，然后将栈顶元素出栈，直到栈为空或者栈顶元素大于等于 $heights[i]$。如果此时栈不为空，说明栈顶元素大于等于 $heights[i]$，那么第 $i$ 个人能看到的人数还要再加 $1$。接下来，如果栈不为空并且栈顶元素等于 $heights[i]$，那么栈顶元素出栈。最后，将 $heights[i]$ 入栈，继续遍历下一个人。

这样处理过后，我们就可以得到每一行每个人能看到的人数。

同理，我们可以对每一列进行处理，得到每一列每个人能看到的人数。最后，我们将每一行和每一列的答案相加，就可以得到最终的答案。

时间复杂度 $O(m\times n)$，空间复杂度 $O(max(m,n))$。其中 $m$ 和 $n$ 分别是数组 $heights$ 的行数和列数。

相似题目：

• 1944. 队列中可以看到的人数

func seePeople(heights [][]int) (ans [][]int) {
	f := func(nums []int) []int {
		n := len(nums)
		ans := make([]int, n)
		stk := []int{}
		for i := n - 1; i >= 0; i-- {
			for len(stk) > 0 && stk[len(stk)-1] < nums[i] {
				ans[i]++
				stk = stk[:len(stk)-1]
			}
			if len(stk) > 0 {
				ans[i]++
			}
			for len(stk) > 0 && stk[len(stk)-1] == nums[i] {
				stk = stk[:len(stk)-1]
			}
			stk = append(stk, nums[i])
		}
		return ans
	}
	for _, row := range heights {
		ans = append(ans, f(row))
	}
	n := len(heights[0])
	for j := 0; j < n; j++ {
		col := make([]int, len(heights))
		for i := range heights {
			col[i] = heights[i][j]
		}
		for i, v := range f(col) {
			ans[i][j] += v
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2345. 寻找可见山的数量 🔒

中等1 种解法

标签：栈、数组、排序、单调栈

题目、示例与约束

给定一个 下标从 0 开始 的二维整数数组 peaks，其中 peaks[i] = [xi, yi] 表示山 i 在坐标 (xi, yi) 处有一个峰值。山可以被描述为一个直角等腰三角形，它的底部沿着 x 轴，山峰处有一个直角。更正式地说，上山和下山的 梯度 分别为 1 和 -1。

一座山如果它的顶峰不在另一座山 (包括其他山的边界) 之内，那么它被认为是 可见 的。

返回可见山的数量。

 

示例 1:

输入: peaks = [[2,2],[6,3],[5,4]]
输出: 2
解释: 上面的图表显示了山脉。
- 山 0 是可见的，因为它的峰值不在另一座山的里面或另一座山的边界。
- 山 1 是不可见的，因为它的顶峰在山 2 的边界。
- 山 2 是可见的，因为它的峰值不在另一座山的里面或另一座山的边界。
有 2 座山是可见的。

示例 2:

输入: peaks = [[1,3],[1,3]]
输出: 0
解释: 上面的图表显示了这些山 (它们完全重叠)。
两座山都看不见，因为它们的山峰在彼此里面。

 

提示:

• 1 <= peaks.length <= 105
• peaks[i].length == 2
• 1 <= xi, yi <= 105

方法一：区间排序 + 遍历 · Go 实现

思考

一座山可见当且仅当它不被另一座完全包含。峰 $(x,y)$ 覆盖区间 $(x-y,x+y)$。完全重合的峰互相遮挡，均不可见。

按左端升序、右端降序排列后扫一遍：右端无法超过当前最右则被包含。仅当该区间出现一次且扩张了最右边界时计入。

我们先将每座山 $(x,y)$ 转换成横坐标的区间 $(x-y,x+y)$，然后对区间按照左端点升序排序，右端点降序排序。

接下来，初始化当前区间的右端点为 $-\mathrm{\infty }$，遍历每座山，如果当前山的右端点小于等于当前区间的右端点，则跳过该山，否则更新当前区间的右端点为当前山的右端点，如果当前山的区间只出现一次，则答案加一。

遍历结束后返回答案即可。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为山的数量。

func visibleMountains(peaks [][]int) (ans int) {
	n := len(peaks)
	type pair struct{ l, r int }
	arr := make([]pair, n)
	for _, p := range peaks {
		x, y := p[0], p[1]
		arr = append(arr, pair{x - y, x + y})
	}
	sort.Slice(arr, func(i, j int) bool { return arr[i].l < arr[j].l || (arr[i].l == arr[j].l && arr[i].r > arr[j].r) })
	cur := math.MinInt32
	for i, e := range arr {
		l, r := e.l, e.r
		if r <= cur {
			continue
		}
		cur = r
		if !(i < n-1 && l == arr[i+1].l && r == arr[i+1].r) {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2390. 从字符串中移除星号

中等1 种解法

标签：栈、字符串、模拟

题目、示例与约束

给你一个包含若干星号 * 的字符串 s 。

在一步操作中，你可以：

• 选中 s 中的一个星号。
• 移除星号 左侧 最近的那个 非星号 字符，并移除该星号自身。

返回移除 所有 星号之后的字符串。

注意：

• 生成的输入保证总是可以执行题面中描述的操作。
• 可以证明结果字符串是唯一的。

 

示例 1：

输入：s = "leet**cod*e"
输出："lecoe"
解释：从左到右执行移除操作：
- 距离第 1 个星号最近的字符是 "leet**cod*e" 中的 't' ，s 变为 "lee*cod*e" 。
- 距离第 2 个星号最近的字符是 "lee*cod*e" 中的 'e' ，s 变为 "lecod*e" 。
- 距离第 3 个星号最近的字符是 "lecod*e" 中的 'd' ，s 变为 "lecoe" 。
不存在其他星号，返回 "lecoe" 。

示例 2：

输入：s = "erase*****"
输出：""
解释：整个字符串都会被移除，所以返回空字符串。

 

提示：

• 1 <= s.length <= 105
• s 由小写英文字母和星号 * 组成
• s 可以执行上述操作

方法一：栈模拟 · Go 实现

思考

每个星号删除其左侧最近的非星号。 $n\le {10}^5$，模拟多次扫描字符串会重复移动。

栈中只保留尚未被删的字母：遇字母入栈，遇星号弹栈。最后拼接即为结果。

我们可以使用栈模拟操作过程。遍历字符串 $s$，如果当前字符不是星号，则将其入栈；如果当前字符是星号，则将栈顶元素出栈。

最后我们将栈中元素拼接成字符串返回即可。

时间复杂度 $O(n)$，其中 $n$ 是字符串 $s$ 的长度。忽略答案字符串的空间消耗，空间复杂度 $O(1)$。

func removeStars(s string) string {
	ans := []rune{}
	for _, c := range s {
		if c == '*' {
			ans = ans[:len(ans)-1]
		} else {
			ans = append(ans, c)
		}
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

2534. 通过门的时间 🔒

困难1 种解法

标签：队列、数组、模拟

题目、示例与约束

n 个人，按从 0 到 n - 1 编号。现在有一扇门，每个人只能通过门进入或离开一次，耗时一秒。

给你一个 非递减顺序 排列的整数数组 arrival ，数组长度为 n ，其中 arrival[i] 是第 i 个人到达门前的时间。另给你一个长度为 n 的数组 state ，其中 state[i] 是 0 则表示第 i 个人希望进入这扇门，是 1 则表示 TA 想要离开这扇门。

如果 同时 有两个或更多人想要使用这扇门，则必须遵循以下规则：

• 如果前一秒 没有 使用门，那么想要 离开 的人会先离开。
• 如果前一秒使用门 进入 ，那么想要 进入 的人会先进入。
• 如果前一秒使用门 离开 ，那么想要 离开 的人会先离开。
• 如果多个人都想朝同一方向走（都进入或都离开），编号最小的人会先通过门。

返回一个长度为 n 的数组 answer ，其中 answer[i] 是第 i 个人通过门的时刻（秒）。

注意：

• 每秒只有一个人可以通过门。
• 为遵循上述规则，一个人可以在到达门附近后等待，而不通过门进入或离开。

 

示例 1：

输入：arrival = [0,1,1,2,4], state = [0,1,0,0,1]
输出：[0,3,1,2,4]
解释：每秒发生的情况如下：
- t = 0 ：第 0 个人是唯一一个想要进入的人，所以 TA 可以直接进入。
- t = 1 ：第 1 个人想要离开，第 2 个人想要进入。因为前一秒有人使用门进入，所以第 2 个人先进入。
- t = 2 ：第 1 个人还是想要离开，第 3 个人想要进入。因为前一秒有人使用门进入，所以第 3 个人先进入。
- t = 3 ：第 1 个人是唯一一个想要离开的人，所以 TA 可以直接离开。
- t = 4 ：第 4 个人是唯一一个想要进入的人，所以 TA 可以直接离开。

示例 2：

输入：arrival = [0,0,0], state = [1,0,1]
输出：[0,2,1]
解释：每秒发生的情况如下：
- t = 0 ：第 1 个人想要进入，但是第 0 个人和第 2 个人都想要离开。因为前一秒没有使用门，所以想要离开的人会先离开。又因为第 0 个人的编号更小，所以 TA 先离开。
- t = 1 ：第 1 个人想要进入，第 2 个人想要离开。因为前一秒有人使用门离开，所以第 2 个人先离开。
- t = 2 ：第 1 个人是唯一一个想要进入的人，所以 TA 可以直接进入。

 

提示：

• n == arrival.length == state.length
• 1 <= n <= 105
• 0 <= arrival[i] <= n
• arrival 按 非递减顺序 排列
• state[i] 为 0 或 1

方法一：队列 + 模拟 · Go 实现

思考

每秒门只让一人通过；两侧都有人时沿用上一秒的方向，空闲后默认先出。按到达时间模拟即可， $n\le {10}^5$ 时需避免每秒空转过久，但到达时间与 $n$ 同阶，逐秒处理仍是线性。

用两个队列分别收进入与离开的请求。时钟 $t$ 前进时把已到达者入队；两队皆非空则弹出门当前方向 $st$ 的队首，仅一队非空则改 $st$ 为该方向，皆空则把门重置为离开。每人的通过时刻写入答案。

我们定义两个队列，其中 $q[0]$ 存放想要进入的人的编号，而 $q[1]$ 存放想要离开的人的编号。

我们维护一个时间 $t$，表示当前时间，一个状态 $st$，表示当前门的状态，当 $st=1$ 表示门没使用或者上一秒有人离开，当 $st=0$ 表示上一秒有人进入。初始时 $t=0$，而 $st=1$。

我们遍历数组 $\mathit{\text{arrival}}$，对于每个人，如果当前时间 $t$ 小于等于该人到达门前的时间 $arrival[i]$，我们将该人的编号加入对应的队列 $q[\text{state}[i]]$ 中。

然后我们判断当前队列 $q[0]$ 和 $q[1]$ 是否都不为空，如果都不为空，我们将 $q[st]$ 队列的队首元素出队，并将当前时间 $t$ 赋值给该人的通过时间；如果只有一个队列不为空，我们根据哪个队列不为空，更新 $st$ 的值，然后将该队列的队首元素出队，并将当前时间 $t$ 赋值给该人的通过时间；如果两个队列都为空，我们将 $st$ 的值更新为 $1$，表示门没使用。

接下来，我们将时间 $t$ 自增 $1$，继续遍历数组 $\mathit{\text{arrival}}$，直到所有人都通过门。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 表示数组 $\mathit{\text{arrival}}$ 的长度。

func timeTaken(arrival []int, state []int) []int {
	n := len(arrival)
	q := [2][]int{}
	t, i, st := 0, 0, 1
	ans := make([]int, n)

	for i < n || len(q[0]) > 0 || len(q[1]) > 0 {
		for i < n && arrival[i] <= t {
			q[state[i]] = append(q[state[i]], i)
			i++
		}

		if len(q[0]) > 0 && len(q[1]) > 0 {
			ans[q[st][0]] = t
			q[st] = q[st][1:]
		} else if len(q[0]) > 0 || len(q[1]) > 0 {
			if len(q[0]) == 0 {
				st = 1
			} else {
				st = 0
			}
			ans[q[st][0]] = t
			q[st] = q[st][1:]
		} else {
			st = 1
		}

		t++
	}

	return ans
}

力扣原题 · Doocs 题解来源

2696. 删除子串后的字符串最小长度

简单1 种解法

标签：栈、字符串、模拟

题目、示例与约束

给你一个仅由 大写 英文字符组成的字符串 s 。

你可以对此字符串执行一些操作，在每一步操作中，你可以从 s 中删除 任一个 "AB" 或 "CD" 子字符串。

通过执行操作，删除所有 "AB" 和 "CD" 子串，返回可获得的最终字符串的 最小 可能长度。

注意，删除子串后，重新连接出的字符串可能会产生新的 "AB" 或 "CD" 子串。

 

示例 1：

输入：s = "ABFCACDB"
输出：2
解释：你可以执行下述操作：
- 从 "ABFCACDB" 中删除子串 "AB"，得到 s = "FCACDB" 。
- 从 "FCACDB" 中删除子串 "CD"，得到 s = "FCAB" 。
- 从 "FCAB" 中删除子串 "AB"，得到 s = "FC" 。
最终字符串的长度为 2 。
可以证明 2 是可获得的最小长度。

示例 2：

输入：s = "ACBBD"
输出：5
解释：无法执行操作，字符串长度不变。

 

提示：

• 1 <= s.length <= 100
• s 仅由大写英文字母组成

方法一：栈 · Go 实现

思考

AB、CD 可删除且可能连锁。反复 replace 最坏平方。相邻可消时与括号匹配相同，栈顶与当前字符恰好组成这两对则弹出，否则入栈。

预先压入空哨兵省去空栈判断，剩余长度减一即答案。

我们遍历字符串 $s$，对于当前遍历到的字符 $c$，如果栈不为空且栈顶元素 $top$ 与 $c$ 可以组成 $AB$ 或 $CD$，则弹出栈顶元素，否则将 $c$ 入栈。

最后栈中剩余的元素个数就是最终字符串的长度。

在实现上，我们可以在栈中预先放入一个空字符，这样就不需要在遍历字符串时判断栈是否为空了，最后返回栈的大小减一即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是字符串 $s$ 的长度。

func minLength(s string) int {
	stk := []byte{' '}
	for _, c := range s {
		if (c == 'B' && stk[len(stk)-1] == 'A') || (c == 'D' && stk[len(stk)-1] == 'C') {
			stk = stk[:len(stk)-1]
		} else {
			stk = append(stk, byte(c))
		}
	}
	return len(stk) - 1
}

力扣原题 · Doocs 题解来源

2751. 机器人碰撞

困难1 种解法

标签：栈、数组、排序、模拟

题目、示例与约束

现有 n 个机器人，编号从 1 开始，每个机器人包含在路线上的位置、健康度和移动方向。

给你下标从 0 开始的两个整数数组 positions、healths 和一个字符串 directions（directions[i] 为 'L' 表示 向左 或 'R' 表示 向右）。 positions 中的所有整数 互不相同 。

所有机器人以 相同速度 同时 沿给定方向在路线上移动。如果两个机器人移动到相同位置，则会发生 碰撞 。

如果两个机器人发生碰撞，则将 健康度较低 的机器人从路线中 移除 ，并且另一个机器人的健康度 减少 1 。幸存下来的机器人将会继续沿着与之前 相同 的方向前进。如果两个机器人的健康度相同，则将二者都从路线中移除。

请你确定全部碰撞后幸存下的所有机器人的 健康度 ，并按照原来机器人编号的顺序排列。即机器人 1 （如果幸存）的最终健康度，机器人 2 （如果幸存）的最终健康度等。 如果不存在幸存的机器人，则返回空数组。

在不再发生任何碰撞后，请你以数组形式，返回所有剩余机器人的健康度（按机器人输入中的编号顺序）。

注意：位置  positions 可能是乱序的。

 

示例 1：

输入：positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = "RRRRR"
输出：[2,17,9,15,10]
解释：在本例中不存在碰撞，因为所有机器人向同一方向移动。所以，从第一个机器人开始依序返回健康度，[2, 17, 9, 15, 10] 。

示例 2：

输入：positions = [3,5,2,6], healths = [10,10,15,12], directions = "RLRL"
输出：[14]
解释：本例中发生 2 次碰撞。首先，机器人 1 和机器人 2 将会碰撞，因为二者健康度相同，二者都将被从路线中移除。接下来，机器人 3 和机器人 4 将会发生碰撞，由于机器人 4 的健康度更小，则它会被移除，而机器人 3 的健康度变为 15 - 1 = 14 。仅剩机器人 3 ，所以返回 [14] 。

示例 3：

输入：positions = [1,2,5,6], healths = [10,10,11,11], directions = "RLRL"
输出：[]
解释：机器人 1 和机器人 2 将会碰撞，因为二者健康度相同，二者都将被从路线中移除。机器人 3 和机器人 4 将会碰撞，因为二者健康度相同，二者都将被从路线中移除。所以返回空数组 [] 。

 

提示：

• 1 <= positions.length == healths.length == directions.length == n <= 105
• 1 <= positions[i], healths[i] <= 109
• directions[i] == 'L' 或 directions[i] == 'R'
• positions 中的所有值互不相同

方法一：栈模拟 · Go 实现

思考

同一直线上的机器人相向碰撞，健康度较小者消失、较大者减一，相同则同归于尽，求按原顺序剩下的健康度。按时间模拟碰撞需要处理多对相遇，坐标范围大。

按位置排序后，向右者入栈，向左者与栈顶连续对撞，直到自身消失或栈中不再有向右者。存活者按原下标筛出健康度仍为正的项。

我们首先将机器人按照位置从小到大排序，用一个数组 $\mathit{\text{idx}}$ 存储排序后的机器人编号。然后我们使用一个栈来模拟碰撞过程：

1. 从左到右遍历 $\mathit{\text{idx}}$ 中的机器人编号 $i$，如果 $directions[i]$ 是向右移动，则将 $i$ 入栈。
2. 如果 $directions[i]$ 是向左移动，则与栈顶的向右移动的机器人发生碰撞，直到栈为空或当前机器人被移除。
   • 如果栈顶机器人健康度大于当前机器人，则当前机器人被移除，栈顶机器人健康度减 1。
   • 如果栈顶机器人健康度小于当前机器人，则栈顶机器人被移除，当前机器人健康度减 1，并继续与新的栈顶机器人发生碰撞。
   • 如果两者健康度相同，则两者都被移除。

最后我们返回所有健康度大于 0 的机器人健康度。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是机器人的数量。

func survivedRobotsHealths(positions []int, healths []int, directions string) []int {
	n := len(positions)
	idx := make([]int, n)
	for i := range idx {
		idx[i] = i
	}

	sort.Slice(idx, func(i, j int) bool {
		return positions[idx[i]] < positions[idx[j]]
	})

	stk := []int{}

	for _, i := range idx {
		if directions[i] == 'R' {
			stk = append(stk, i)
			continue
		}

		for len(stk) > 0 && healths[i] > 0 {
			j := stk[len(stk)-1]

			if healths[j] > healths[i] {
				healths[j]--
				healths[i] = 0
			} else if healths[j] < healths[i] {
				healths[i]--
				healths[j] = 0
				stk = stk[:len(stk)-1]
			} else {
				healths[i], healths[j] = 0, 0
				stk = stk[:len(stk)-1]
				break
			}
		}
	}

	ans := []int{}
	for _, h := range healths {
		if h > 0 {
			ans = append(ans, h)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源