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

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

共 6 个回复

题目

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

可以这样,
先从左到右遍历,求一个leftMax数组,记录nums[i]左边的最大值;
再从右到左遍历求一个rightMin数组,记录nums[i]右边的最小值。
然后从左到右遍历每个元素,如果某元素满足leftMax[i]<nums[i]<=rightMin[i],则求得该数

2

和楼上思路类似,不过尝试用单调栈只扫描数组一次。

首先算法基于 “寻找右侧最近较小元素” 算法,这题可以用单调栈来做。这样,扫描过后留在单调栈里的元素都满足小于等于右侧所有元素,但这样无法保证大于左侧所有元素。

我们可以思考入栈元素在什么情况下会小于左侧元素 - 那就是在弹栈之后插入的元素。我们可以用一个变量保存此前已弹出的最大元素值,并仅在新元素值大于该值的情况下才入栈。

示例代码

  public int[] findMidElement(int[] arr) {

    Deque<Integer> monoStack = new LinkedList<>();

    int localPeek = Integer.MIN_VALUE;
    for (int value : arr) {
      while (!monoStack.isEmpty() && monoStack.peek() > value) {
        localPeek = Math.max(localPeek, monoStack.poll());
      }
      if (value >= localPeek) {
        monoStack.push(value);
      }
    }

    int[] ret = new int[monoStack.size()];
    int size = monoStack.size();
    for (int i = size - 1; i >= 0; i--)
      ret[i] = monoStack.poll();

    return ret;
  }
1

维持一个不严格(可相等)的递增栈,同时记录到此为止的最大值.只要栈里的第一个 >= 最大值,可能就是可以满足的了.

1

请问这个是leetcode上面的哪道题呢

nth_element的思想