Интуиция позади использования монотонного стека

Question

Я решаю вопрос на LeetCode.com :

Учитывая массив целых чисел A, найдите сумму min (B), где B лежит в каждом (смежном) подмассиве A. Поскольку ответ может быть большим, вернуть ответ по модулю 10 ^ 9 + 7.

Ввод : [3,1,2,4]
Выход : 17
Пояснение : Подмассивами являются [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2 ], [1,2,4], [3,1,2,4]. Минимум 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Сумма составляет 17 *. 1016 *

A решение с высоким рейтингом , как показано ниже:

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;
  }
};

Мой вопрос: какова интуиция в использовании монотонно увеличивающегося стека для этого? Как это помогает вычислить минимумы в различных подмассивах?

Answer 1

Визуализация массива в виде линейного графика с (локальными) минимумами в виде долин.Каждое значение относится к диапазону , который простирается от сразу после предыдущего меньшего значения (если оно есть) до непосредственно следующего меньшего значения (если оно есть).(Даже значение, большее, чем у его соседей, имеет значение при рассмотрении содержащего его одноэлементного подмассива.) Переменные left и right отслеживают этот диапазон.

Признавая, что значение shadows каждыезначение, превышающее его в каждом направлении в отдельности, в стеке поддерживается список предыдущих, незатененных минимумов для двух целей: определения того, насколько далеко простирается диапазон нового небольшого числа, и (в то же время), насколько далеко простираются диапазоны недействительных минимумов.Код использует отдельный стек для каждой цели, но в этом нет необходимости: каждый из них содержит одинаковое содержимое после каждой итерации (внешнего) цикла.