1094. Range Assign, Range Max
A warehouse tracks the stock level of each shelf along one long aisle. Managers often reset a whole stretch of shelves to the same level and then ask for the highest level within some stretch. Design RangeAssign to support both actions efficiently.
RangeAssign(nums)starts withnums[i]as the level of shelfi.assign(left, right, value)sets every shelf with index fromlefttoright(both included) to exactlyvalue.maxRange(left, right)returns the largest level among shelveslefttoright(both included).
Levels can be negative and 0 is an ordinary level like any other. Touching every shelf of the range on each call is too slow for long aisles with many requests.
Example 1
- Input:
- operations = ["RangeAssign","maxRange","assign","maxRange","maxRange","assign","maxRange"]arguments = [[[4,9,2,7,5]],[0,4],[1,3,3],[0,4],[1,3],[0,4,-8],[2,4]]
- Output:
- [null,9,null,5,3,null,-8]
- Explanation:
The maximum is 9; after setting shelves 1..3 to 3 the maximum becomes 5, the middle stretch is all 3, and finally every shelf is -8.
Example 2
- Input:
- operations = ["RangeAssign","assign","maxRange","maxRange"]arguments = [[[-5,-9]],[0,0,0],[0,1],[1,1]]
- Output:
- [null,null,0,-9]
- Explanation:
Assigning 0 is a real assignment: the maximum of both shelves becomes 0, while shelf 1 alone is still -9.
Constraints
1 ≤ nums.length ≤ 105
-109 ≤ nums[i], value ≤ 109
0 ≤ left ≤ right < nums.length; at most 105 operations
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(log n) per operation after an O(n) build
- Space
- O(n)