leetcode

commit b7b5fc681ddc1c0c7ff307680ac29ebf49508950
parent 7afe9d85ae8503e3a6ff01329325693512cd15f0
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 26 Jun 2024 18:19:45 +0200

1 Random Problem

Diffstat:
A
Problems/0962.cpp
 | 
18
++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 19 insertions(+), 0 deletions(-)
diff --git a/Problems/0962.cpp b/Problems/0962.cpp
@@ -0,0 +1,18 @@
+class Solution {
+  public:
+    int maxWidthRamp(const vector<int> &nums) const {
+        vector<pair<int, int>> vec;
+        int res = 0;
+
+        for (int i = 0; i < size(nums); i++) {
+            if (empty(vec) || vec.back().first > nums[i])
+                vec.emplace_back(nums[i], i);
+            else {
+                const auto opt = lower_bound(begin(vec), end(vec), make_pair(nums[i], INT_MAX), greater());
+                res = max(res, i - opt->second);
+            }
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -593,6 +593,7 @@ for solving problems.
 |  0956  |   Medium   | [Tallest Billboard](Problems/0956.cpp)                                                             |
 |  0958  |   Medium   | [Check Completeness of a Binary Tree](Problems/0958.cpp)                                           |
 |  0959  |   Medium   | [Regions Cut By Slashes](Problems/0959.cpp)                                                        |
+|  0962  |   Medium   | [Maximum Width Ramp](Problems/0962.cpp)                                                            |
 |  0965  |    Easy    | [Univalued Binary Tree](Problems/0965.cpp)                                                         |
 |  0966  |   Medium   | [Vowel Spellchecker](Problems/0966.cpp)                                                            |
 |  0967  |   Medium   | [Numbers With Same Consecutive Differences](Problems/0967.cpp)                                     |