Skip to content

Latest commit

 

History

History
106 lines (88 loc) · 4.4 KB

README.md

File metadata and controls

106 lines (88 loc) · 4.4 KB

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

Companies: Amazon

Related Topics:
Array, Dynamic Programming, Stack, Monotonic Stack

Similar Questions:

Hints:

  • Create a dp array where dp[i] is the maximum number of books you can take if you can only take books from bookshelves 0 to i and you must take books from bookshelf i.
  • Keep taking as many books as you can (i.e. starting from bookshelf i and going backwards, you take arr[i], arr[i] - 1, arr[i] - 2, … books).
  • You may reach an index j where arr[j] < arr[i] - (i - j). Have we already found the maximum number of books you can take from bookshelves 0 to j? How do we quickly find such an index j?
  • Keep a stack of possible indices for j. If x is the number at the top of the stack, keep popping from the stack while arr[x] ≥ arr[i] - (i - x). This is because if the inequality mentioned before is true, x will never be an index j as index i will run out of items first.

Solution 1. Stack

// OJ: https://leetcode.com/problems/maximum-number-of-books-you-can-take
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    long long maximumBooks(vector<int>& A) {
        long long N = A.size(), sum = 0, ans = 0;
        stack<long long> idx, val;
        for (int i = 0; i < N; ++i) {
            while (idx.size() && i - idx.top() >= A[i] - A[idx.top()]) {
                idx.pop();
                sum -= val.top();
                val.pop();
            }
            long long prev = idx.size() ? idx.top() : -1, len = min(i - prev, (long long)A[i]);
            idx.push(i);
            long long s = A[i] * len - len * (len - 1) / 2;
            sum += s;
            ans = max(ans, sum);
            val.push(s);
        }
        return ans;
    }
};