Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

Topic describes

Give you n non-negative integers A1, A2… Each number represents a point in the coordinates (I, ai). Draw n vertical lines in the coordinates, and the two endpoints of vertical line I are (I, AI) and (I, 0). Find the two lines that together with the X-axis will hold the most water.

Note: You cannot tilt the container.

Max ((i-j)*min(a[I],a[j])), I > j.

We find that when a[j]>=a[I], min value is a[I], so the smaller j is, the better. Those js satisfying a[j]>=a[I] can constitute an answer value ANS1, ans1 is not necessarily equal to the final answer. What if a[j]<a[I]? Reverse the array and do it again! Let’s call this ans2, so Max (ans1,ans2) is the answer.

So we just need the smallest j, such that a[j]>=a[I].

Solution 1: line segment tree.

The line tree maintains the interval Max. If the left interval Max >=a[I], the left is recursed, otherwise the right is recursed.


let ls = x= > (x << 1), rs = x= > (x << 1 | 1)
let nd = new Array(200010).fill(0)
​
function build(x, l, r, a) {
  if (l === r) {
    nd[x] = a[l - 1]
    return
  }
  let mid = (l + r) >> 1
  build(ls(x), l, mid, a)
  build(rs(x), mid + 1, r, a)
  nd[x] = Math.max(nd[ls(x)], nd[rs(x)])
}
​
function query(x, l, r, v) {
  if (l === r) return l
  let mid = (l + r) >> 1
  if (nd[ls(x)] >= v) return query(ls(x), l, mid, v)
  return query(rs(x), mid + 1, r, v)
}
​
var maxArea = function(a) {
  const n = a.length
  let solve = (a) = > {
    build(1.1, n, a)
    let ans = 0
    for (let i = 0; i < n; ++i) {
      let idx = query(1.1, n, a[i]) - 1
      if (idx > i) continue
      ans = Math.max(ans, a[i] * (i - idx))
    }
    return ans
  }
  let ans = solve(a)
  a.reverse()
  ans = Math.max(ans, solve(a))
  return ans
};
Copy the code

Solution 2: sort + suffix min

Bind values and subscripts together and sort them in ascending order, or at will if they are the same. Let’s call that b array.

Find the first subscript IDx greater than or equal to A [I], then min(b[IDx ~n-1][1]) (0-indexed) is obtained. Hence the suffix min.

var maxArea = function(a) {
  const n = a.length
  let lower_bound = (a, x) = > {
    let l = 0, r = a.length
    while (l < r) {
      let mid = (l + r) >> 1
      if (a[mid] >= x) r = mid
      else l = mid + 1
    }
    return l
  }
  let solve = (a) = > {
    let b = a.map((v, i) = > [v, i])
    b.sort((x, y) = > x[0] ^ y[0]? x[0] - y[0] : x[1] - y[1])
    let val = b.map(v= > v[0]), mn = b.map(v= > v[1])
    for (let i = n - 2; ~i; --i) mn[i] = Math.min(mn[i], mn[i + 1])
    let ans = 0
    for (let i = 0; i < n; ++i) {
      let idx = lower_bound(val, a[i])
      ans = Math.max(ans, a[i] * (i - mn[idx]))
    }
    return ans
  }
  let ans = solve(a)
  a.reverse()
  ans = Math.max(ans, solve(a))
  return ans
};
Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤