题目形容
这是 LeetCode 上的 901. 股票价格跨度 ，难度为 中等。
Tag :「分块」、「枯燥栈」
编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
明天股票价格的跨度被定义为股票价格小于或等于明天价格的最大间断日数（从明天开始往回数，包含明天）。
例如，如果将来 7 天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
示例：
输出：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输入：[null,1,1,1,2,1,4,6]
解释：首先，初始化 S = StockSpanner()，而后：S.next(100) 被调用并返回 1，S.next(80) 被调用并返回 1，S.next(60) 被调用并返回 1，S.next(70) 被调用并返回 2，S.next(60) 被调用并返回 1，S.next(75) 被调用并返回 4，S.next(85) 被调用并返回 6。留神 (例如) S.next(75) 返回 4，因为截至明天的最初 4 个价格
(包含明天的价格 75) 小于或等于明天的价格。提醒：
- 调用
StockSpanner.next(int price)时，将有 $1 <= price <= 10^5$。 - 每个测试用例最多能够调用
10000次StockSpanner.next。 - 在所有测试用例中，最多调用
150000次StockSpanner.next。 - 此问题的总工夫限度缩小了
50%。
分块
又名优雅的暴力。
这是一道在线问题，在调用 next 往数据流存入元素的同时，返回间断段不大于以后元素的数的个数。
一个奢侈的想法是：应用数组 nums 将所有 price 进行存储，每次返回时往前找到第一个不满足要求的地位，并返回间断段的长度。
但对于 $10^4$ 的调用次数来看，该做法的复杂度为 $O(n^2)$，计算量为 $10^8$，不满足 OJ 要求。
实际上咱们能够利用「分块」思路对其进行优化，将与间断段的比拟转换为与最值的比拟。
具体的，咱们依然应用 nums 对所有的 price 进行存储，同时应用 region 数组来存储每个间断段的最大值，其中 $region[loc] = x$ 含意为块编号为 loc 的最大值为 x，其中块编号 loc 块对应了数据编号 idx 的范畴 $[(loc – 1) \times len + 1, loc \times len]$。
对于 next 操作而言，除了间接更新数据数组 nums[++idx] = price 以外，咱们还须要更新 idx 所在块的最值 region[loc]，而后从以后块 loc 开始往前扫描其余块，应用 left 和 right 代指以后解决到的块的左右端点，若以后块满足 region[loc] <= price，阐明块内所有元素均满足要求，间接将以后块 loc 所蕴含元素个数累加到答案中，直到遇到不满足的块或达到块数组边界，若存在遇到不满足要求的块，再应用 right 和 left 统计块内满足要求 nums[i] <= price 的个数。
对于块个数和大小的设定，是使用分块升高复杂度的要害，数的个数为 $10^4$，咱们能够设定块大小为 $\sqrt{n} = 100$，这样也限定了块的个数为 $\sqrt{n} = 100$ 个。这样对于单次操作而言，咱们最多遍历进行 $\sqrt{n}$ 次的块间操作，同时最多进行一次块内操作，整体复杂度为 $O(\sqrt{n})$，单次 next 操作计算量为 $2 \times 10^2$ 以内，单样例计算量为 $2 \times 10^6$，能够过。
为了不便，咱们令块编号 loc 和数据编号 idx 均从 $1$ 开始；同时为了避免每个样例都 new 大数组，咱们采纳 static 优化，并在 StockSpanner 的初始化中做重置工作。
Java 代码：
class StockSpanner {
static int N = 10010, len = 100, idx = 0;
static int[] nums = new int[N], region = new int[N / len + 10];
public StockSpanner() {for (int i = 0; i <= getIdx(idx); i++) region[i] = 0;
idx = 0;
}
int getIdx(int x) {return (x - 1) / len + 1;
}
int query(int price) {int ans = 0, loc = getIdx(idx), left = (loc - 1) * len + 1, right = idx;
while (loc >= 1 && region[loc] <= price) {
ans += right - left + 1;
loc--; right = left - 1; left = (loc - 1) * len + 1;
}
for (int i = right; loc >= 1 && i >= left && nums[i] <= price; i--) ans++;
return ans;
}
public int next(int price) {nums[++idx] = price;
int loc = getIdx(idx);
region[loc] = Math.max(region[loc], price);
return query(price);
}
}TypeScript 代码：
class StockSpanner {
N: number = 10010; sz: number = 100; idx: number = 0
nums: number[] = new Array<number>(this.N).fill(0);
region = new Array<number>(Math.floor(this.N / this.sz) + 10).fill(0)
getIdx(x: number): number {return Math.floor((x - 1) / this.sz) + 1
}
query(price: number): number {let ans = 0, loc = this.getIdx(this.idx), left = (loc - 1) * this.sz + 1, right = this.idx
while (loc >= 1 && this.region[loc] <= price) {
ans += right - left + 1
loc--; right = left - 1; left = (loc - 1) * this.sz + 1
}
for (let i = right; loc >= 1 && i >= left && this.nums[i] <= price; i--) ans++
return ans
}
next(price: number): number {this.nums[++this.idx] = price
const loc = this.getIdx(this.idx)
this.region[loc] = Math.max(this.region[loc], price)
return this.query(price)
}
}Python3 代码：
class StockSpanner:
def __init__(self):
self.N, self.sz, self.idx = 10010, 110, 0
self.nums, self.region = [0] * self.N, [0] * (self.N // self.sz + 10)
def next(self, price: int) -> int:
def getIdx(x):
return (x - 1) // self.sz + 1
def query(price):
ans, loc = 0, getIdx(self.idx)
left, right = (loc - 1) * self.sz + 1, self.idx
while loc >= 1 and self.region[loc] <= price:
ans += right - left + 1
loc -= 1
right, left = left - 1, (loc - 1) * self.sz + 1
while loc >= 1 and right >= left and self.nums[right] <= price:
right, ans = right - 1, ans + 1
return ans
self.idx += 1
loc = getIdx(self.idx)
self.nums[self.idx] = price
self.region[loc] = max(self.region[loc], price)
return query(price)- 工夫复杂度：因为应用了
static优化，StockSpanner初始化时，须要对上一次应用的块进行重置，复杂度为 $O(\sqrt{n})$；因为块大小和数量均为 $\sqrt{n}$，next操作复杂度为 $O(\sqrt{n})$ - 空间复杂度：$O(n)$
枯燥栈
另外一个容易想到的想法是应用「枯燥栈」，栈内以二元组 $(idx, price)$ 模式保护比以后元素 price 大的元素。
每次执行 next 操作时，从栈顶开始解决，将所有满足「不大于 price」的元素进行出栈，从而找到以后元素 price 右边最近一个比其大的地位。
Java 代码：
class StockSpanner {Deque<int[]> d = new ArrayDeque<>();
int cur = 0;
public int next(int price) {while (!d.isEmpty() && d.peekLast()[1] <= price) d.pollLast();
int prev = d.isEmpty() ? -1 : d.peekLast()[0], ans = cur - prev;
d.addLast(new int[]{cur++, price});
return ans;
}
}TypeScript 代码：
class StockSpanner {stk = new Array<Array<number>>(10010).fill([0, 0])
he = 0; ta = 0; cur = 0
next(price: number): number {while (this.he < this.ta && this.stk[this.ta - 1][1] <= price) this.ta--
const prev = this.he >= this.ta ? -1 : this.stk[this.ta - 1][0], ans = this.cur - prev
this.stk[this.ta++] = [this.cur++, price]
return ans
}
}Python3 代码：
class StockSpanner:
def __init__(self):
self.stk = []
self.cur = 0
def next(self, price: int) -> int:
while self.stk and self.stk[-1][1] <= price:
self.stk.pop()
prev = -1 if not self.stk else self.stk[-1][0]
ans = self.cur - prev
self.stk.append([self.cur, price])
self.cur += 1
return ans- 工夫复杂度：
next操作的均摊复杂度为 $O(1)$ - 空间复杂度：$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.901 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布