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 <= 1050 <= books[i] <= 105
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| 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)
}
|
