【递增栈】个人练习-Leetcode-845. Longest Mountain in Array-Toy模板网

这篇具有很好参考价值的文章主要介绍了【递增栈】个人练习-Leetcode-845. Longest Mountain in Array。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接：https://leetcode.cn/problems/longest-mountain-in-array/

题目大意：给出一个数组arr[]，定义【山数组】为【长度大于等于3】【前面部分递增，后面部分递减，存在一个山峰元素】的数组。求arr[]中的最长的是【山数组】的子列。

思路：递增栈当然可以，不过刚好想到另一个写法，感觉还行，于是就这么做了。维护两个数组left[], right[]，left[i]表示从i开始向左递减（即可以作为山峰的左半段）最远的下标；同理，right[i]表示从i开始向右递减（即可以作为山峰的右半段）最远的下标。那么如果一个【山数组】以i为山峰，其长度就是right[i] - left[i] + 1。最开始初始化所有left[i] = right[i] = i，因为如果无法延伸（不递减），那么就是到自己为止。

对于left[]，从左往右遍历，如果是从左往右递增（即从右往左递减）就将左边的下标“传递”过去。显然left[i] <= i，它的目的是从i尽可能往左延伸，下标越左越好。

对于right[]，从右往左遍历，如果是从右往左递增（即从左往右递减）就将右边的下标“传递”过去。显然right[i] >= i，它的目的是从i尽可能往右延伸，下标越右越好。

因为山数组的长度大于等于3，因此遍历山峰只需从下标1到N-2就好了。注意山数组需要【左边和右边都至少长度为1】，只有左半边或者右半边的不能构成山数组！遍历，保留最长的长度即可。

完整代码文章来源地址https://www.toymoban.com/news/detail-455025.html

class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int N = arr.size();
        vector<int> left(N, 0);
        vector<int> right(N, 0);
        for (int i = 0; i < N; i++)
            left[i] = right[i] = i;
        
        for (int i = 0; i < N-1; i++) {
            if (arr[i] < arr[i+1])
                left[i+1] = left[i];
        }

        for (int i = N-1; i > 0; i--) {
            if (arr[i] < arr[i-1])
                right[i-1] = right[i];
        }

        int ans = 0;
        for (int i = 1; i < N-1; i++) {
            int lp = i - left[i], rp = right[i] - i;
            if (lp && rp) {
                int len = lp + rp + 1;
                ans = max(ans, len);
            }   
        }

        return ans;
    }
};