讨论/题目交流/求一道算法题/
求一道算法题

给出一个元素无序的数组,求出一个数,使得其左边的数都小于它,右边的数都大于等于它。
要求时间复杂度n

展开讨论
15.10发起于 2020-03-16

题目

原描述:
给出一个元素无序的数组,求出一个数,使得其左边的数都小于它,右边的数都大于等于它。
要求时间复杂度n

整理及丰富细节:
一个无序的数组,找出所有符合以下特点的数,返回它们的索引。
这个数的左边的数都小于它,右边的数都大于等于它。
要求时间复杂度 O(n) 。

思路

  1. 使用单调栈
    11. 当元素入栈的时候,单调栈只能保证入栈元素比栈内元素都大,但是不能保证是数组中出现过的最大的
    12. 所以额外需要一个最大值,来增强入栈规则
    13. 出栈的元素曾经是满足条件的,但是现在出现更大的数字,不符合规则,被淘汰

图解

图片.png

用例

输入:[3,2,1,4,7,6,5]
输出:[3]

输入:[2,1,3,4,5,7,6]
输出:[2,3,4]

输入:[7,6,5,4,3,2,1]
输出:[]

输入:[6,5,4,3,2,1,7]
输出:[6]

输入:[1,7,6,5,4,3,2]
输出:[0]

答题

vector<int> getMidNum(vector<int>& nums) {
    vector<int> ans;
    int maxn = INT_MIN;
    for (int i = 0; i < nums.size(); i++) {
        while (!ans.empty() && !(nums[ans.back()] < nums[i])) {
            ans.pop_back();
        }

        if (nums[i] > maxn) {
            ans.push_back(i);
        }

        maxn = max(maxn, nums[i]);
    }
    return ans;
}

模拟

输入:[2,1,3,4,5,7,6]
输出:[2,3,4]
=============================================================================
2,1,3,4,5,7,6,

i = 0
        [push]
        ans:    2,
        maxn = 2

i = 1
        [pop]
        ans:
        maxn = 2

i = 2
        [push]
        ans:    3,
        maxn = 3

i = 3
        [push]
        ans:    3,4,
        maxn = 4

i = 4
        [push]
        ans:    3,4,5,
        maxn = 5

i = 5
        [push]
        ans:    3,4,5,7,
        maxn = 7

i = 6
        [pop]
        ans:    3,4,5,
        maxn = 7

Result =
[2,3,4]

///////////////////////////////////////////////////////////// time:   2.86 ms

致谢

如果有理解错,或者答错,欢迎指出。

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

我的leetcode

4
展开全部 6 讨论