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

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

展开讨论

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

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

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

示例代码

  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
展开全部 6 讨论