# 算法合集 | 神奇的笛卡尔树 - HDU 1506

1、笛卡尔树的构造：

（1）从第一个元素开始，从左往右遍历数组L

（2）将元素L[0]作为树的根节点R

（3）for i in [a[1], a[2]...a[n]]

（4）如果a[i]小于根节点R，则将a[i]作为根节点R的父节点

（5）如果a[i]大于根节点R，则将a[i]从根节点的右节点开始寻找位置

（6）从右寻找的逻辑同根节点的对比方法

2、特性

```#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct node_s
{
struct node_s * l;
struct node_s * r;
struct node_s * p;
int v;
}node_t;

typedef struct tree_s
{
node_t * root;
}tree_t;

node_t * node_create(node_t * p, int v)
{
node_t * n = (node_t*)malloc(sizeof(node_t));
memset(n, 0, sizeof(node_t));
n->v = v;
n->p = p;
return n;
}

tree_t * tree_create()
{
tree_t * t = (tree_t*)malloc(sizeof(tree_t));
memset(t, 0, sizeof(tree_t));
return t;
}

void tree_insert_n(node_t * root, int v)
{
//当前节点比根节点小，则转换为根节点
if(v < root->v){
node_t * n = node_create(root->p, v);
root->p->r = n;
root->p = n;
n->l = root;
}else{
//如果右子树不存在，直接放置
if(root->r == 0){
root->r = node_create(root, v);
return;
}
//当前的节点比根节点大，则从根节点的右子树开始查找
tree_insert_n(root->r, v);
}
}

void tree_insert(tree_t * t, int v)
{
if(t->root == 0){
t->root = node_create(0, v);
return;
}

//当前节点比根节点小，则转换为根节点
if(v < t->root->v){
node_t * n = node_create(0, v);
t->root->p = n;
n->l = t->root;
t->root = n;
}else{
//如果右子树不存在，直接放置
if(t->root->r == 0){
t->root->r = node_create(t->root, v);
return;
}
//当前的节点比根节点大，则从根节点的右子树开始查找
tree_insert_n(t->root->r, v);
}
}

void tree_print_n(node_t * n, int level, char dir)
{
if(!n){
return;
}
for(int i=0; i<level; ++i){
printf("---");
}
printf("%c--%d\n", dir, n->v);
tree_print_n(n->l, level+1, 'L');
tree_print_n(n->r, level+1, 'R');
}

void tree_print(tree_t * tree)
{
tree_print_n(tree->root, 0, 'C');
printf("\n");
}

void tree_free(tree_t * t)
{

}

int main()
{
freopen("test.txt", "r", stdin);

int n, height;

while (scanf("%d", &n), n)
{
int arr[n];

tree_t * tree = tree_create();

for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}

for (int i = 0; i < n; ++i)
{
tree_insert(tree, arr[i]);
tree_print(tree);
}

tree_free(tree);

printf("\n");
}

return 0;
}```

Problem Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 <= n <= 100000. Then follow n integers h1, ..., hn, where 0 <= hi <= 1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

```7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0```

Sample Output

`8 4000`

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int N = 100000 + 10, INF = 0x3f3f3f3f;

struct node
{
int index;
int value;
int parent;
int child[2];

friend bool operator< (node a, node b)
{
return a.index < b.index;
}

void init(int _index, int _value, int _parent)
{
index = _index;
value = _value;
parent = _parent;

child[0] = child[1] = 0;
}

} tree[N];

int root;
int top, stk[N];
ll ans;

//创建笛卡尔树
int cartesian_build(int n)
{
for (int i = 1; i <= n; i++)
{
int k = i - 1;

//一直找到比i位置小的位置k
while (tree[k].value > tree[i].value)
k = tree[k].parent;

//printf("i(%d - %d) k(%d - %d)\n", i, tree[i].value, k, tree[k].value);

//将父节点的右子树放到自己的左子树上
tree[i].child[0] = tree[k].child[1];
//父节点的右子树重新指向
tree[k].child[1] = i;
//设置i的父节点
tree[i].parent = k;
//很多人没加这句，父节点关系就会乱掉
tree[tree[i].child[0]].parent = i;
}

return tree[0].child[1];
}

int dfs(int x)
{
if (!x)
return 0;
//计算最大值
int sz = dfs(tree[x].child[0]);
sz += dfs(tree[x].child[1]);
ans = max(ans, (ll)(sz + 1) * tree[x].value);
return sz + 1;
}

int main()
{
int n, height;
//freopen("test.txt", "r", stdin);

while (scanf("%d", &n), n)
{
tree[0].init(0, 0, 0);

for (int i = 1; i <= n; i++)
{
scanf("%d", &height);
//初始化每个节点
tree[i].init(i, height, 0);
}

//创建笛卡尔树
root = cartesian_build(n);
//
ans = 0;
dfs(root);
printf("%lld\n", ans);
}

return 0;
}```

220 篇文章34 人订阅

0 条评论

## 相关文章

4400

13120

### 二叉树的遍历：先序中序后序遍历的递归与非递归实现及层序遍历

对于一种数据结构而言，遍历是常见操作。二叉树是一种基本的数据结构，是一种每个节点的儿子数目都不多于2的树。二叉树的节点声明如下： 1 typedef str...

35860

### [LeetCode] 129. Sum Root to Leaf Numbers

【原题】 Given a binary tree containing digits from 0-9 only, each root-to-leaf pa...

224100

33540

19650

57120

12320

15840

### 用OC和Swift一起说说二叉树

一：在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）...

10850