LeetCode 2355. Maximum Number of Books You Can Take Solution in Java, C++, Python & Go | Explanation + Code

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³), where n is the number of rows or columns in the matrix grid. The space complexity is O(1).

PythonJavaC++Go

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(code-box)

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; } }(code-box)

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; } };(code-box)

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) }(code-box)