🔧 962. Maximum Width Ramp
Nachrichtenbereich: 🔧 Programmierung
🔗 Quelle: dev.to
962. Maximum Width Ramp
Difficulty: Medium
Topics: Array
, Stack
, Monotonic Stack
A ramp in an integer array nums
is a pair (i, j)
for which i < j
and nums[i] <= nums[j]
. The width of such a ramp is j - i
.
Given an integer array nums
, return the maximum width of a ramp in nums
. If there is no ramp in nums
, return 0
.
Example 1:
- Input: nums = [6,0,8,2,1,5]
- Output: 4
- Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): nums[1] = 0 and nums[5] = 5.
Example 2:
- Input: nums = [9,8,1,0,1,9,4,0,4,1]
- Output: 7
- Explanation: The maximum width ramp is achieved at (i, j) = (2, 9): nums[2] = 1 and nums[9] = 1.
Constraints:
2 <= nums.length <= 5 * 104
0 <= nums[i] <= 5 * 104
Solution:
We can leverage the concept of a monotonic stack. Here's the solution and explanation:
Approach:
-
Monotonic Decreasing Stack: We create a stack that keeps track of indices of elements in a way such that
nums[stack[i]]
is in a decreasing order. This allows us to later find pairs(i, j)
wherenums[i] <= nums[j]
. -
Traverse from the End: After creating the stack, we traverse the array from the end (
j
fromn-1
to0
) to try and find the farthesti
for eachj
wherenums[i] <= nums[j]
. -
Update the Maximum Width: Whenever
nums[i] <= nums[j]
holds for the current top of the stack, calculate the ramp widthj - i
and update the maximum width if it's larger.
Let's implement this solution in PHP: 962. Maximum Width Ramp
<?php
/**
* @param Integer[] $nums
* @return Integer
*/
function maxWidthRamp($nums) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example 1
$nums = [6, 0, 8, 2, 1, 5];
echo maxWidthRamp($nums); // Output: 4
// Example 2
$nums = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1];
echo maxWidthRamp($nums); // Output: 7
?>
Explanation:
-
Create a Decreasing Stack:
- Iterate through the array and add indices to the stack.
- Only add an index if it corresponds to a value that is less than or equal to the value of the last index in the stack. This ensures that values in the stack are in a decreasing order.
-
Traverse from the End:
- As we go backward through the array, for each
j
, pop indicesi
from the stack as long asnums[i] <= nums[j]
. - Calculate the width
j - i
and updatemaxWidth
.
- As we go backward through the array, for each
-
Why This Works:
- By maintaining a decreasing stack of indices, we ensure that when we encounter a
j
with a larger value, it can give us a larger widthj - i
wheni
is popped from the stack.
- By maintaining a decreasing stack of indices, we ensure that when we encounter a
-
Time Complexity:
- Building the stack takes
O(n)
time since each index is pushed once. - The traversal from the end and popping indices also takes
O(n)
since each index is popped at most once. - Overall, the solution runs in
O(n)
time, which is efficient for input size up to5 * 10^4
.
- Building the stack takes
Output:
- For
nums = [6, 0, 8, 2, 1, 5]
, the output is4
, corresponding to the ramp(1, 5)
. - For
nums = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1]
, the output is7
, corresponding to the ramp(2, 9)
.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
...
🔧 962. Maximum Width Ramp
📈 74.57 Punkte
🔧 Programmierung
🕵️ Maximum: Wrong link on corne.maximum.nl
📈 25.96 Punkte
🕵️ Sicherheitslücken
💾 Webmin 1.962 Remote Command Execution
📈 24.36 Punkte
💾 IT Security Tools
💾 Webmin 1.962 Remote Command Execution
📈 24.36 Punkte
💾 IT Security Tools
🔧 Day 962 : All I Need
📈 24.36 Punkte
🔧 Programmierung
⚠️ Webmin 1.962 Remote Command Execution
📈 24.36 Punkte
⚠️ PoC
🔧 How to quickly ramp up on new codebases
📈 19.35 Punkte
🔧 Programmierung