Leetcode Problem:
Summary
- Find the maximum value over all triplets of indices (i, j, k) such that i < j < k in the given array nums.
Approach
- The approach used is to use a stack to store the elements of the array
- We iterate over the array and for each element, we update the maximum distance between the smallest and largest elements in the stack
- We also update the maximum value by multiplying the maximum distance with the current element
- If the current element is greater than the top of the stack, we remove elements from the stack until the top of the stack is less than or equal to the current element
- Finally, we return the maximum value found.
Complexity
- O(n log n) due to the sorting operation inside the while loop
Explanation
- The solution code uses a stack to store the elements of the array
- We iterate over the array and for each element, we update the maximum distance between the smallest and largest elements in the stack
- We also update the maximum value by multiplying the maximum distance with the current element
- If the current element is greater than the top of the stack, we remove elements from the stack until the top of the stack is less than or equal to the current element
- This is done to ensure that the stack always contains the smallest and largest elements seen so far
- Finally, we return the maximum value found.
Solution Code:
class Solution {
public:
long long maximumTripletValue(vector& nums) {
long long ans = 0;
int maxDist = 0;
vector st;
for(int i = 0; i < nums.size(); i++){
if(st.size() >= 2){
maxDist = max(maxDist, st[0] - st.back());
}
ans = max(ans, (long long)maxDist * nums[i]);
while(!st.empty() && st.back() < nums[i]){
st.pop_back();
}
st.push_back(nums[i]);
}
return ans;
}
};
class Solution {
public:
long long maximumTripletValue(vector& nums) {
long long ans = 0;
int maxDist = 0;
vector st;
for(int i = 0; i < nums.size(); i++){
if(st.size() >= 2){
maxDist = max(maxDist, st[0] - st.back());
}
ans = max(ans, (long long)maxDist * nums[i]);
while(!st.empty() && st.back() < nums[i]){
st.pop_back();
}
st.push_back(nums[i]);
}
return ans;
}
};
'알고리즘' 카테고리의 다른 글
| Maximum Value of an Ordered Triplet I (0) | 2025.04.03 |
|---|---|
| Solving Questions With Brainpower (0) | 2025.04.01 |
| Put Marbles in Bags (0) | 2025.04.01 |
| Partition Labels (0) | 2025.03.30 |
| Apply Operations to Maximize Score (0) | 2025.03.29 |
짬뽕얼큰하게