LeetCode 1499: Max Value of Equation
Problem Description
Explanation:
- We can iterate through the points array, keeping track of the maximum value of yi + yj + |xi - xj| that we have encountered so far.
- To maximize the equation yi + yj + |xi - xj|, we can rewrite it as (yi - xi) + (yj + xj). This way, for each point j, we only need to find the maximum value of (yi - xi) for all previous points i.
- We can use a deque to store the indices of points where the difference (yi - xi) is maximum, within a range of k.
- By maintaining a decreasing order deque based on the value (yi - xi), we can easily find the maximum value within the range k.
- We iterate through the points array, updating the deque and calculating the maximum value of the equation.
Time Complexity: O(n) Space Complexity: O(n) :
Solutions
class Solution {
public int findMaxValueOfEquation(int[][] points, int k) {
Deque<Integer> deque = new LinkedList<>();
int maxVal = Integer.MIN_VALUE;
for (int[] point : points) {
while (!deque.isEmpty() && point[0] - points[deque.peekFirst()][0] > k) {
deque.pollFirst();
}
if (!deque.isEmpty()) {
maxVal = Math.max(maxVal, point[1] + points[deque.peekFirst()][1] + point[0] - points[deque.peekFirst()][0]);
}
while (!deque.isEmpty() && point[1] - point[0] > points[deque.peekLast()][1] - points[deque.peekLast()][0]) {
deque.pollLast();
}
deque.offerLast(points.indexOf(point));
}
return maxVal;
}
}Loading editor...