- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用?
- database - RESTful URI 是否应该公开数据库主键?
我正在解决关于 LeetCode.com 的问题:
Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A. Since the answer may be large, return the answer modulo 10^9 + 7.
Input: [3,1,2,4]
Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17.
class Solution {
public:
int sumSubarrayMins(vector<int>& A) {
stack<pair<int, int>> in_stk_p, in_stk_n;
// left is for the distance to previous less element
// right is for the distance to next less element
vector<int> left(A.size()), right(A.size());
//initialize
for(int i = 0; i < A.size(); i++) left[i] = i + 1;
for(int i = 0; i < A.size(); i++) right[i] = A.size() - i;
for(int i = 0; i < A.size(); i++){
// for previous less
while(!in_stk_p.empty() && in_stk_p.top().first > A[i]) in_stk_p.pop();
left[i] = in_stk_p.empty()? i + 1: i - in_stk_p.top().second;
in_stk_p.push({A[i],i});
// for next less
while(!in_stk_n.empty() && in_stk_n.top().first > A[i]){
auto x = in_stk_n.top();in_stk_n.pop();
right[x.second] = i - x.second;
}
in_stk_n.push({A[i], i});
}
int ans = 0, mod = 1e9 +7;
for(int i = 0; i < A.size(); i++){
ans = (ans + A[i]*left[i]*right[i])%mod;
}
return ans;
}
};
我的问题是:为此使用单调递增的堆栈背后的直觉是什么?它如何帮助计算各个子数组中的最小值?
最佳答案
将数组可视化为折线图,(局部)最小值为谷。每个值都与一个范围相关,该范围从前一个较小值(如果有)之后延伸到下一个较小值(如果有)之前。 (在考虑包含它的单例子数组时,即使值大于其邻居也很重要。)变量 left
和 right
跟踪该范围。
认识到一个值在每个方向上分别遮蔽每个大于它的值,堆栈维护一个先前的、未遮蔽的最小值的列表,用于两个目的:识别一个新的小数字的范围向后延伸多远以及(同时)无效的最小值范围向前延伸多远。该代码为每个目的使用了一个单独的堆栈,但没有必要:在(外部)循环的每次迭代之后,每个堆栈都有相同的内容。
关于c++ - 使用单调堆栈背后的直觉,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55780200/
我正在寻找一种快速方法来使 pandas 数据帧在 x 中单调。 我当前的解决方案如下: def make_monotonic(df, cols=None): """make df monot
CLOCK_REALTIME 的一个问题是它不是单调的,如果发生 NTP 同步,时间可能会倒退。 像下面这样的事情让它变得单调是否安全? struct timespec GetMonotonicTim
我是一名优秀的程序员,十分优秀!