单调区间怎么求？详解算法及实现

单调区间指的是一个序列中值单调递增或单调递减的连续区间。求解序列中所有的单调区间是一个非常基础的算法问题，但在实际应用中也有很重要的作用。比如在股票分析中，往往需要对股票价格序列做单调区间分析，以便找到波动较大的时间段，从而制定相应的投资策略。

下面将介绍两种常见的单调区间求解算法：暴力法和单调栈法。

暴力法

暴力法是最朴素的求解单调区间的方法。其基本思想是枚举所有可能的区间，然后判断这些区间是否单调。

vector<pair<int, int>> monotonic_intervals(const vector<int>& nums) {    vector<pair<int, int>> res;    const int n = nums.size();    for (int i = 0; i < n; ++i) {        for (int j = i + 1; j <= n; ++j) {            bool inc = true, dec = true;            for (int k = i + 1; k < j; ++k) {                inc = inc && nums[k] >= nums[k - 1];                dec = dec && nums[k] <= nums[k - 1];            }            if (inc || dec) res.emplace_back(i, j - 1);        }    }    return res;}

上述代码中，monotonic_intervals 函数接受一个整数序列 nums，返回所有的单调区间。具体实现中，我们枚举所有的可能区间，然后再遍历该区间内的数字，判断区间是否单调递增或单调递减。若满足条件，则保存该区间的起止位置。

暴力法的时间复杂度是O(n^3)，空间复杂度是O(n)。显然，暴力法只适用于较小规模的问题，对于大规模数据则显得力不从心。

单调栈法

单调栈法是一种更为高效的单调区间求解算法，它的核心思想是维护一个单调递增或单调递减的栈，栈中存储的是数组中每个元素的下标。当遇到一个新元素时，若其比栈顶元素大（或小），则将其入栈；否则，不停地将栈中元素弹出，直到遇到一个比当前元素小（或大）的元素为止。这样可以保证栈中的元素始终是一个单调递增（或递减）的序列。

下面给出单调递增栈的一个简单实现。

vector<int> incr_dfs(const vector<int>& nums) {    const int n = nums.size();    vector<int> res(n);    stack<int> s;    for (int i = 0; i < n; ++i) {        while (!s.empty() && nums[i] > nums[s.top()]) {            res[s.top()] = i - s.top();            s.pop();        }        s.push(i);    }    while (!s.empty()) {        res[s.top()] = n - s.top();        s.pop();    }    return res;}

incr_dfs 函数接受一个整数序列 nums，并返回一个新的序列 res，其中 res[i] 表示 nums 中从位置 i 开始的第一个较大元素距离 i 的距离。

具体实现中，我们维护了一个单调递增栈 s，遍历输入序列 nums，当遇到一个比栈顶元素大的元素时，我们将栈顶的元素出栈，并记录其离当前位置的距离。由于当前元素比栈顶元素大，因此显然这个栈顶元素在以后的算法中不可能再成为答案的一部分，故我们将其出栈。最后，将当前元素入栈。当遍历结束时，我们需要将栈中剩余的元素处理掉。由于当前元素是序列的最后一个元素，且序列中不存在比它更大的元素了，因此我们可以将栈中的元素一一出栈，并将 res 对应的位置置为 n - s.top()。

对于单调递减的栈，实现方法与上述代码类似，只需将比较符号改成小于即可。

使用单调栈法求解单调区间的时间复杂度是 O(n)，空间复杂度也是 O(n)。可以看到，单调栈法相比于暴力法具有更高的效率。当然，单调栈法不能处理所有的单调区间问题，例如，它无法处理存在重复元素的问题。