Tag Archives:

LeetCode Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Given an array of integers nums and an integer limit, return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to limit.

In case there is no subarray satisfying the given condition return 0.

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 0 <= limit <= 10^9

给定一个数组,问数组中一个连续的子数组内的最大值和最小值的差不超过limit的最长连续子数组的长度。

常规解法。使用DP求出任何一个子区间dp[i,j]的最大值和最小值,dp[i,j+1]的最大值和最小值只需要用nums[j]和dp[i,j]的最大值和最小值比较即可。完整代码如下:

class Solution {
public:
	int longestSubarray(vector<int>& nums, int limit) {
		int n = nums.size();
		int ans = 1; // 最小值是1

		for (int i = 0; i < n; ++i) {
			vector<int> dp_max(n, 0), dp_min(n, INT_MAX);
			dp_max[i] = dp_min[i] = nums[i];
			for (int len = 2; len <= n; ++len) {
				int j = i + len - 1;
				if (j >= n)break;
				dp_max[j] = max(dp_max[j - 1], nums[j]);
				dp_min[j] = min(dp_min[j - 1], nums[j]);
				int diff = dp_max[j] - dp_min[j];
				if (diff <= limit) {
					ans = max(ans, j - i + 1);
				}
				else {
					break;
				}
			}
		}
		return ans;
	}
};

很不幸,该代码的时间复杂度达到了O(n^2),在最后两个测试样例上TLE了。

比O(n^2)低的复杂度有O(nlgn)和O(n)。O(nlgn)排序好像无法求解,那么只有O(n)的方法了。此题本质上是一个滑动窗口的问题,可以用两个指针i和j,标记区间的起止位置。那么问题的关键就是如何快速求解到区间[i,j]的最大值和最小值。

我之前的方法是用DP提前算出来,但是DP的过程费时。使用优先队列priority_queue(最大堆、最小堆)可以得到当前区域的最大值和最小值,但是一旦差的绝对值超过limit,需要从优先队列中删除i所指元素时,priority_queue没有提供erase或者remove之类的接口,所以使用priority_queue无法达成目标。

提示使用multiset,我之前知道multiset内部使用红黑树结构,内部存储是有序的,而且提供了erase接口以供删除元素。但是我一直不确定如何获得multiset内部的最大值和最小值元素,虽然它内部是有序的,但我不确定程序员能否得到其有序列表。

后来看了multiset的API,里面明确说明了multiset默认是从小到大排序,而且其begin()指向最小值rbegin()指向最后一个元素,即最大值。所以multiset是一个功能很强大的容器,它不但可以实现堆的功能,还能查找、删除某个元素,比 priority_queue 更强大。

使用multiset的完整代码如下:

class Solution {
public:
    int longestSubarray(vector<int>& A, int limit) {
        int res = 0, n = A.size(), i = 0, j;
        multiset<int> m;
        for (j = 0; j < n; ++j) {
            m.insert(A[j]);
            if (*m.rbegin() - *m.begin() > limit)
                m.erase(m.find(A[i++]));
            else
                res=max(res,j-i+1);
        }
        return res;
    }
};

本代码提交AC,用时368MS。

另外,我们还可以指定multiset内部的排序规则,让其表现为最大堆或最小堆。

LeetCode Last Stone Weight

1046. Last Stone Weight

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together.  Suppose the stones have weights x and y with x <= y.  The result of this smash is:

  • If x == y, both stones are totally destroyed;
  • If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.)

Example 1:

Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

Note:

  1. 1 <= stones.length <= 30
  2. 1 <= stones[i] <= 1000

给定一个数组,每个数表示一个石头的质量,每次从数组中选两个最终的石头,如果相等,则两个石头都砸碎,不相等这把质量差再次放入数组。问最终剩余质量是多少。

简单模拟题,使用最大堆来装所有石头的质量,代码如下:

class Solution {
public:
	int lastStoneWeight(vector<int>& stones) {
		priority_queue<int,vector<int>,std::less<int>> pq(stones.begin(),stones.end());
		while (pq.size() >= 2) {
			int first = pq.top();
			pq.pop();
			int second = pq.top();
			pq.pop();

			if (first != second)pq.push(first - second);
		}
		if (pq.size() == 0)return 0;
		else return pq.top();
	}
};

本代码提交AC,用时0MS。

LeetCode Maximum Performance of a Team

1383. Maximum Performance of a Team

There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers. 

Example 1:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

Example 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

Example 3:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

Constraints:

  • 1 <= n <= 10^5
  • speed.length == n
  • efficiency.length == n
  • 1 <= speed[i] <= 10^5
  • 1 <= efficiency[i] <= 10^8
  • 1 <= k <= n

给定n个工程师,每个工程师有自己的速度值speed和效率值efficiency,一个包含k个工程师的团队的总体performance等于所有工程师的速度之和乘以最小效率:sum(speed)*min(efficiency)。问最多选k个工程师,最大的performance是多少。

我一开始被“最多k个”迷惑了,一直以为是一个DP题,后来看题解发现不是。

由于performance=sum(speed)*min(efficiency),所以首先对n个工程师按efficiency从大到小排序,然后对于前m个工程师,他们的最小efficiency就是当前遍历到的第m个工程师的efficiency。如果m已经超过k,则需要从m个工程师中剔除掉速度最小的工程师,因为此时的min(efficiency)固定是第m个工程师的efficiency,所以只需要剔除速度低的工程师。

那么,如果最优解是少于k个人,这种方法能否找到最优解呢?其实是可以的,因为对于每加入一个工程师,我们都会和当前最优解对比,刚开始的时候,队列中的人数肯定少于k。

完整代码如下:

class Solution {
public:
	int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
		vector<pair<int, int>> workers;
		for (int i = 0; i < n; ++i) {
			workers.push_back(make_pair(efficiency[i], speed[i]));
		}
		sort(workers.begin(), workers.end()); // 默认对pair.first升序排列
		priority_queue <int, vector<int>, greater<int> > pq; // pq默认是最大堆,这是构建最小堆
		long long ans = 0;
		long long sum_speed = 0;
		for (int i = n - 1; i >= 0; --i) {
			sum_speed += workers[i].second;
			pq.push(workers[i].second);
			if (pq.size() > k) {
				sum_speed -= pq.top();
				pq.pop();
			}
			ans = max(ans, sum_speed*workers[i].first);
		}
		return ans % (int)(1e9 + 7);
	}
};

本代码提交AC,用时108MS。

LeetCode Merge k Sorted Lists

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

归并k个已排序的链表。 之前是归并2个已排序的链表,现在变成多个了。其实就是多路归并,思路之前都知道,不同思路的区别就在于怎样找到所有链表当前位置的最小值,可以直接线性查找,也可以用败者树、胜者树或者堆。我一开始用线性查找,不出意外的TLE了,后来改用建堆的方法,顺利通过。 写代码越来越懒了,直接上STL,需要注意的是STL中的make_heap默认建的是大顶堆,我们需要传自己的比较函数进去以便构建小顶堆。

typedef struct Node {
    ListNode* ln;
    int idx;
    bool operator<(const Node& p) const { return this->ln->val < p.ln->val; }
    bool operator>(const Node& p) const { return this->ln->val > p.ln->val; }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        ListNode *ans = new ListNode(0), *head = ans;
        vector<Node> vn;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] != NULL) {
                Node nd;
                nd.ln = lists[i];
                nd.idx = i;
                vn.push_back(nd);
                lists[i] = lists[i]->next;
            }
        }
        if (vn.size() == 0)
            return NULL;
        make_heap(vn.begin(), vn.end(), greater<Node>());
        while (true) {
            Node tmp = vn.front();
            ans->next = tmp.ln;
            ans = ans->next;
            pop_heap(vn.begin(), vn.end(), greater<Node>());
            vn.pop_back();
            if (lists[tmp.idx] != NULL) {
                tmp.ln = lists[tmp.idx];
                vn.push_back(tmp);
                push_heap(vn.begin(), vn.end(), greater<Node>());
                lists[tmp.idx] = lists[tmp.idx]->next;
            }
            if (vn.empty())
                break;
        }
        return head->next;
    }
};

本代码提交AC,用时420MS。

二刷。更简单的是直接使用STL的优先队列,代码如下:

struct LNNode {
	ListNode* ln;
	LNNode() :ln(NULL) {};
	bool operator<(const LNNode& ln_) const{ // 注意两个const都不能少
		return ln->val > ln_.ln->val;
	}
};
class Solution {
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		priority_queue<LNNode> pq;
		for (int i = 0; i < lists.size(); ++i) {
			if (lists[i] != NULL) {
				LNNode cur;
				cur.ln = lists[i];
				pq.push(cur);
			}
		}
		ListNode* root = new ListNode(0);
		ListNode* ans = root;
		while (!pq.empty()) {
			LNNode cur = pq.top();
			pq.pop();
			root->next = cur.ln;
			root = root->next;
			if (cur.ln->next) {
				LNNode nxt;
				nxt.ln = cur.ln->next;
				pq.push(nxt);
			}
		}
		return ans->next;
	}
};

本代码提交AC,用时32MS。

或者不用定义新的类,直接用原来的ListNode*,但新增一个比较函数,代码如下:

struct cmp {
	bool operator()(ListNode* l1, ListNode* l2) {
		return l1->val > l2->val;
	}
};

class Solution {
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
		for (int i = 0; i < lists.size(); ++i) {
			if (lists[i] != NULL) {
				pq.push(lists[i]);
			}
		}
		ListNode* root = new ListNode(0);
		ListNode* ans = root;
		while (!pq.empty()) {
			ListNode* cur = pq.top();
			pq.pop();
			root->next = cur;
			root = root->next;
			if (cur->next) {
				pq.push(cur->next);
			}
		}
		return ans->next;
	}
};

本代码提交AC,用时32MS。