Question

2355. Maximum Number of Books You Can Take

中文文档

Description

You are given a 0-indexed integer array books of length n where books[i] denotes the number of books on the ith shelf of a bookshelf.

You are going to take books from a contiguous section of the bookshelf spanning from l to r where 0 <= l <= r < n. For each index i in the range l <= i < r, you must take strictly fewer books from shelf i than shelf i + 1.

Return _the maximum number of books you can take from the bookshelf._

 

Example 1:

Input: books = [8,5,2,7,9]
Output: 19
Explanation:
- Take 1 book from shelf 1.
- Take 2 books from shelf 2.
- Take 7 books from shelf 3.
- Take 9 books from shelf 4.
You have taken 19 books, so return 19.
It can be proven that 19 is the maximum number of books you can take.

Example 2:

Input: books = [7,0,3,4,5]
Output: 12
Explanation:
- Take 3 books from shelf 2.
- Take 4 books from shelf 3.
- Take 5 books from shelf 4.
You have taken 12 books so return 12.
It can be proven that 12 is the maximum number of books you can take.

Example 3:

Input: books = [8,2,3,7,3,4,0,1,4,3]
Output: 13
Explanation:
- Take 1 book from shelf 0.
- Take 2 books from shelf 1.
- Take 3 books from shelf 2.
- Take 7 books from shelf 3.
You have taken 13 books so return 13.
It can be proven that 13 is the maximum number of books you can take.

 

Constraints:

• 1 <= books.length <= 105
• 0 <= books[i] <= 105

Solutions

Solution 1: Simulation

We directly compare each row and column of the matrix $grid$. If they are equal, then it is a pair of equal row-column pairs, and we increment the answer by one.

The time complexity is $O(n^3)$, where $n$ is the number of rows or columns in the matrix $grid$. The space complexity is $O(1)$.

class Solution:
  def maximumBooks(self, books: List[int]) -> int:
    nums = [v - i for i, v in enumerate(books)]
    n = len(nums)
    left = [-1] * n
    stk = []
    for i, v in enumerate(nums):
      while stk and nums[stk[-1]] >= v:
        stk.pop()
      if stk:
        left[i] = stk[-1]
      stk.append(i)
    ans = 0
    dp = [0] * n
    dp[0] = books[0]
    for i, v in enumerate(books):
      j = left[i]
      cnt = min(v, i - j)
      u = v - cnt + 1
      s = (u + v) * cnt // 2
      dp[i] = s + (0 if j == -1 else dp[j])
      ans = max(ans, dp[i])
    return ans

class Solution {
  public long maximumBooks(int[] books) {
    int n = books.length;
    int[] nums = new int[n];
    for (int i = 0; i < n; ++i) {
      nums[i] = books[i] - i;
    }
    int[] left = new int[n];
    Arrays.fill(left, -1);
    Deque<Integer> stk = new ArrayDeque<>();
    for (int i = 0; i < n; ++i) {
      while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        left[i] = stk.peek();
      }
      stk.push(i);
    }
    long ans = 0;
    long[] dp = new long[n];
    dp[0] = books[0];
    for (int i = 0; i < n; ++i) {
      int j = left[i];
      int v = books[i];
      int cnt = Math.min(v, i - j);
      int u = v - cnt + 1;
      long s = (long) (u + v) * cnt / 2;
      dp[i] = s + (j == -1 ? 0 : dp[j]);
      ans = Math.max(ans, dp[i]);
    }
    return ans;
  }
}

using ll = long long;

class Solution {
public:
  long long maximumBooks(vector<int>& books) {
    int n = books.size();
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) nums[i] = books[i] - i;
    vector<int> left(n, -1);
    stack<int> stk;
    for (int i = 0; i < n; ++i) {
      while (!stk.empty() && nums[stk.top()] >= nums[i]) stk.pop();
      if (!stk.empty()) left[i] = stk.top();
      stk.push(i);
    }
    vector<ll> dp(n);
    dp[0] = books[0];
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
      int v = books[i];
      int j = left[i];
      int cnt = min(v, i - j);
      int u = v - cnt + 1;
      ll s = 1ll * (u + v) * cnt / 2;
      dp[i] = s + (j == -1 ? 0 : dp[j]);
      ans = max(ans, dp[i]);
    }
    return ans;
  }
};

func maximumBooks(books []int) int64 {
  n := len(books)
  nums := make([]int, n)
  left := make([]int, n)
  for i, v := range books {
    nums[i] = v - i
    left[i] = -1
  }
  stk := []int{}
  for i, v := range nums {
    for len(stk) > 0 && nums[stk[len(stk)-1]] >= v {
      stk = stk[:len(stk)-1]
    }
    if len(stk) > 0 {
      left[i] = stk[len(stk)-1]
    }
    stk = append(stk, i)
  }
  dp := make([]int, n)
  dp[0] = books[0]
  ans := 0
  for i, v := range books {
    j := left[i]
    cnt := min(v, i-j)
    u := v - cnt + 1
    s := (u + v) * cnt / 2
    dp[i] = s
    if j != -1 {
      dp[i] += dp[j]
    }
    ans = max(ans, dp[i])
  }
  return int64(ans)
}