大樓輪廓 算法解析

題目來源 點選打開連結

這道題經過好多次修改，，最主要是時間複雜度問題。

下面講講思路：

第一個重要轉化是将所有矩形轉變為向上跳變和向下跳變兩種情況。之後對所有的上跳變和下跳變排序。用vector。

需要另一個容器用來維護目前的高度。目前重疊高度height必須是一個可檢索的存儲方式。

height一開始使用vector 但是涉及到非常多的插入和删除操作，是以改為連結清單，而且使用不删除的形式，連結清單中每個節點使用一個count來實作該高度是否存在。

bool operator< (const Rect_fun &a) const

這個邏輯很重要，對于建立好的上下跳變的vector，首先根據x進行排序（x小的排在前面），其次對于相同的x，根據flag排序，flag==1向上跳變排在前面，最後對于相同x相同flag，向上跳變的高度排在前面，向下跳變的高度排在後面。

struct HeightNode
{
	int h;
	int count;
	HeightNode *next;

	HeightNode(int hh, int cc): h(hh), count(cc), next(NULL){}
};
int findHeightMax(HeightNode *ptr)
{
	int max = 0;
	while(ptr != NULL)
	{
		if(ptr->h > max && ptr->count > 0)
			max = ptr->h;
		ptr = ptr->next;
	}
	return max;
}
int getHeightSize(HeightNode *ptr)//可優化
{
	int count=0;
	while(ptr != NULL)
	{
		count += ptr->count;
		ptr = ptr->next;
	}
	return count;
}
void deleteHeight(HeightNode *ptr, int ii)
{
	while(ptr != NULL)
	{
		if(ptr->h == ii)
		{
			ptr->count--;
		}
		ptr = ptr->next;
	}
}
void addHeight(HeightNode *ptr, int ii)
{
	while(1)
	{
		if(ptr->h == ii)
		{
			ptr->count++;
			return ;
		}
		if(ptr->next != NULL)
			ptr = ptr->next;
		else
			break;
	}
	//如果沒找到
	HeightNode *p = new HeightNode(ii,1);
	ptr->next = p;
	

}

 struct Rect_fun
{
    int x;
    bool flag;//1是向上跳變 0是向下跳變
	int height;
	
	Rect_fun(int xx, int f, int h) : x(xx), flag(f), height(h){}

	//對于向量元素是結構體的，可在結構體内部定義比較函數，下面按照id,length,width升序排序。
	bool operator< (const Rect_fun &a)  const
    {
		if(x != a.x)
			return x<a.x;
		else
		{
			if(flag !=a.flag)
				return flag>a.flag;
			else
			{
				if(flag==1)
					return height>a.height;
				else
					return height<a.height;
			}
		}
    }
};

class Solution {
public:
    /**
     * @param buildings: A list of lists of integers
     * @return: Find the outline of those buildings
     */
    
	vector<vector<int>> buildingOutline(vector<vector<int> > &buildings) {

		vector<vector<int>> out;//輸出的結果
		vector<Rect_fun> state;

		vector<int> now_height;//目前的高度
		HeightNode p_item(0,0);
		HeightNode *p_height = &p_item;
		

		int height_temp = 0;
		int height_x = 0;//向上跳變時x的起點
		bool height_flag = 0;//是否在建構新的矩形

		for(int i=0; i<buildings.size(); i++)//獲得跳變沿的資訊，之後對所有跳變沿排序
		{
			Rect_fun temp1(buildings.at(i).at(0), 1, buildings.at(i).at(2));
			Rect_fun temp2(buildings.at(i).at(1), 0, buildings.at(i).at(2));
			state.push_back(temp1);
			state.push_back(temp2);
		}
		sort(state.begin(),state.end());

		for(int i=0; i<state.size(); i++)
		{
			if(state.at(i).flag == 1)//如果是上升沿
			{
				//now_height.push_back(state.at(i).height);
				addHeight(p_height,state.at(i).height);
				if(0 == height_flag)//如果之前沒有矩形
				{
					height_x = state.at(i).x;//記錄下目前跳變沿的位置
					height_temp = state.at(i).height;//記錄下目前的高度
					height_flag = 1;
				}
				else
				{
					if(state.at(i).height > height_temp)
					{
						vector<int> temp;
						temp.push_back(height_x);
						temp.push_back(state.at(i).x);
						temp.push_back(height_temp);
						out.push_back(temp);

						height_x = state.at(i).x;
						height_temp = state.at(i).height;
					}
				}
			}
			if(state.at(i).flag == 0)//如果是下降沿
			{
				//vector<int>::iterator iter=find(now_height.begin(), now_height.end(), state.at(i).height);
				//now_height.erase(iter);
				deleteHeight(p_height, state.at(i).height);

				//if(now_height.size() != 0)
				if(getHeightSize(p_height) != 0)
				{
					if(state.at(i).height != height_temp)//當去除的節點不是最大值，可以忽略
					{
						continue;
					}
					//int max_temp = *max_element(now_height.begin(),now_height.end());
					int max_temp = findHeightMax(p_height);
                    if(max_temp <  height_temp  && height_x != state.at(i).x)//目前向下跳變比之前低,如果想下跳是最大值，但是有兩個最大值，這句話可以避免問題
					{
					vector<int> temp;
					temp.push_back(height_x);
					temp.push_back(state.at(i).x);
					temp.push_back(height_temp);
					out.push_back(temp);

					height_x = state.at(i).x;
					height_temp = max_temp;
					}
					
				}
				else//向下跳變到0
				{
					vector<int> temp;
					temp.push_back(height_x);
					temp.push_back(state.at(i).x);
					temp.push_back(height_temp);
					out.push_back(temp);

					height_x = 0;
					height_temp =0;
					height_flag = 0;

				}
			}
		}
		return out;
        // write your code here
    }
};